Matrix 450 DSA Love Babbar | Priyanshu Tiwari

Table Of Content

Search a node in BST

Search a node in BST #

Given a matrix of size r*c. Traverse the matrix in spiral form.

GFG

The idea is to use the fact that the given tree is a BST. So, instead of transverting every node, we can use the binary search algorithm.

Time Complexity : O(m*n)
Space Complexity : O(1)

bool search(Node* root, int x) {
    
    if (!root) return false;
    
    while(root){       
        if(root->data == x)
            return true;
        
         if(root->data < x)
            root = root->right;
         else
            root = root->left;   
    }

    return false;
}