Search given key in BST | Recursive & Iterative Solution

Given a BST, write an efficient function to search a given key in it. The algorithm should return the parent node of the key and print if the key is left or right node of the parent node. If the key is not present in the BST, the algorithm should be able to determine that.

Searching a binary search tree for a specific key can be programmed recursively or iteratively.

Search given key in BST

We begin by examining the root node. If the tree is null, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node. If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than that of the root, we search the right subtree. This process is repeated until the key is found or the remaining subtree is null. If the searched key is not found after a null subtree is reached, then the key is not present in the tree. This is easily expressed as a recursive algorithm.


Download   Run Code


Download   Run Code

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

The same algorithm can be implemented iteratively.


Download   Run Complete Code


Download   Run Code

In the worst case this algorithm must search from the root of the tree to the leaf farthest from the root, the search operation takes time proportional to the tree’s height. On average, binary search trees with n nodes have O(log n) height. However, in the worst case, binary search trees can have O(n) height (for skewed trees where all the nodes except leaf have one and only one child), when the unbalanced tree resembles a linked list.

See Also:

1. Insertion in BST

2. Deletion from BST


1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of
Abhishek Sharma

The iterative implementation is wrong. It prints every node as root node.