BST | 450 DSA | Love Babbar

Posted on Jan 1, 0001

Search a node in BST

Given a Binary Search Tree and a node value X, find if the node with value X is present in the BST or not.

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. {: .prompt-tip }

  • Time Complexity : O(h)
  • Space Complexity : O(1)
bool search(Node* root, int x) {

    if (!root) return false;

        if(root->data == x)
            return true;

         if(root->data < x)
            root = root->right;
            root = root->left;

    return false;