Searching in a Binary Search Tree (Implementation)
Explore how to implement both iterative and recursive search functions for binary search trees in C++. Understand the traversal logic and analyze the search operation's time complexity to write efficient BST search code.
Introduction #
In this lesson, we’ll implement a search function for binary search trees, which will return a node from the tree if the value to be searched matches it. We’ll again implement both an iterative and a recursive solution.
Here is a high-level description of the algorithm:
-
Set the
current nodeequal to root. -
If the value is less than the
current node's value, then move on to the left subtree, otherwise move on to the right sub-tree -
Repeat until the value at the
current nodeis equal to the value searched, or it becomesNULL. -
Return the current node ...