Search in a Binary Search Tree

Problem Statement: Given the root of a binary search tree and an integer value say x. We have to find the node in the BST such that the node's value is equal to x. If it exits in BST then return true, otherwise false.
A binary tree is considered as BST if it satisfies below conditions:

The left subtree of a node contains only nodes with values less than the node's value.
The right subtree of a node contains only nodes with values greater than the node's value.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [10,8,25,5,9,22], x = 22
Output: true

Example 2:

Input: root = [10,8,25,5,9,22], x = 4
Output: false

Approach:

The approach is simple we will take benefit from the property of BST. We have seen that left subtree of a node contains only nodes with values less than the node's value and right subtree of a node contains only nodes with values greater than the node's value. Hence we will start from root if x is smaller than current node's value we will go to left subtree else if the x is greater than current node's value we will try searching x in right subtree if both of these conditions is not excecuted that means we have found a node whose value is equal to x and return true.
If we got root equal to null means we haven't found any node with value equal to x. Hence, return false.

Code Implementation:

Java

public class SearchBST {
    
    //Constructor
    static class Node {
        int data;
        Node left, right;

        Node(int key) {
            data = key;
            left = right = null;
        }
    }

    public static void main(String[] ans) {
        /*
         * Creating Binary Search Tree The created BST is same as in the above given
         * figure (refer figure for reference)
         */
        Node root = new Node(10);
        root.left = new Node(8);
        root.right = new Node(25);
        root.left.left = new Node(5);
        root.left.right = new Node(9);
        root.right.left = new Node(22);

        int x = 22; /* Value to be searched */
        System.out.println(searchBST(root, x));

    }

    private static boolean searchBST(Node root, int x) {
        /*
         * if root is null means we haven't found node
         * with value x hence return false
         */
        if (root == null)
            return false;

        if (x < root.data) {
            /*
             * if x is smaller than root.data
             * so it must be in left subtree
             */

            return searchBST(root.left, x);
        } else if (x > root.data) {
            /*
             * if x is greater it means x should be in right subtree so search in
             * rightsubtree
             */

            return searchBST(root.right, x);
        } else {
            /*
             * if above two conditions are not true it means we have got node value which is
             * equal to x thus return true
             */
            return true;
        }
    }
}

Output:

true

Complexity Analysis:

Time Complexity: O(h), where h is the height of binary tree.

Space Complexity: O(n), Considering the stack space where n is number of nodes visited.

If you want to contribute such articles to solutions2coding.com please click here. Thank you!