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.

C++

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.

C++

Download   Run Complete 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.
 

Insertion in BST

Deletion from BST

 
References: https://en.wikipedia.org/wiki/Binary_search_tree

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz