Prerequisites :- Binary Search Trees, BinaryTree traversal.
Problem:- Given a binary search tree and an integer X, search if X exists in the BST or not.
(Note: A binary search tree is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node’s left subtree and less than the ones in its right subtree.)
Solution Approach:-
This problem can be solved using any of the normal binary tree traversal methods(inorder, preorder or postorder), however, an efficient search algorithm can be written using the BST property (The node value of any node is greater than all nodes’ values in its left subtree and less than all nodes’ values in its right subtree.).
Hence, instead of going through each node to match the value with given X, we can prune the search by going only in required subtree (see the code for more clarification). What we mean is if X is greater than the root node’s value, then search in the right subtree else search it in the left subtree.
Time complexity :- O(N), because in the worst case, the algorithm might visit all the nodes in the given BST.
Space complexity :- O(1), as no extra space is needed.