Search a Node in BST

Problem

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

Examples:

Example 1:

Input:
               2
                \
                 81 
               /    \ 
             42      87 
              \       \ 
               66      90 
              / 
            45
X = 87
Output: 1
Explanation: As 87 is present in the given nodes , so the output will be 1.

Example 2:

Input: 
            6
             \ 
              8 
             / \ 
            7   9
X = 11
Output: 0
Explanation: As 11 is not present in the given nodes , so the output will be 0.

Your task:

You don't need to read input or print anything. Complete the function search() which returns true if the node with value x is present in the BSTelse returns false.

• Expected Time Complexity: $O$(Height of the BST)
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=$Number of Nodes$<=10^5$

Solution

Python

def search(self, node, x):
    if node is None:
        return False
    if x == node.data:
        return True
    elif x < node.data:
        return self.search(node.left, x)
    else:
        return self.search(node.right, x)

Java

boolean search(Node root, int x) {
    if (root == null)
        return false;
    if (x == root.data)
        return true;
    else if (x < root.data)
        return search(root.left, x);
    else
        return search(root.right, x);
}

C++

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

C

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

• Time Complexity: $O$(Height of the BST)
• Auxiliary Space: $O(1)$