Home Matrix | 450 DSA | Love Babbar
Post
Cancel

Matrix | 450 DSA | Love Babbar

Search a node in BST

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

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
This post is licensed under CC BY 4.0 by the author.

C++ | Ladder 4 | a2oj

Sorting | 450 DSA | Love Babbar