Searching and Traversal in BST
Explore how to perform efficient searching and traversal in Binary Search Trees (BSTs) using both recursive and iterative approaches in C++. Understand the BST properties that enable fast search operations and evaluate their time complexity depending on tree structure. Gain practical knowledge to implement and optimize BST searches for balanced and unbalanced scenarios.
Searching is one of the main reasons binary search trees (BSTs) are so useful. Because a BST follows a specific ordering rule, we do not need to check every node one by one. Instead, at each step, we can decide whether to move left or right.
In a BST (with duplicates allowed):
All values in the left subtree are smaller than the node.
All values in the right subtree are greater than or equal to the node.
This property makes searching much faster than searching in a normal binary tree.
How searching works
To search for a target value in a BST:
Start at the root.
Compare the target with the current node.
If the target is equal to the current node, the search is successful.
If the target is smaller, move to the left subtree.
If the target is greater than or equal to the current node, move to the right subtree.
Repeat until:
The value is found.
We reach
None, which means the value is not in the tree.
This step-by-step process works because the BST ordering tells us exactly where a value can or cannot be.
Example
For example, consider this BST:
Now suppose we want to search for
Step 1: Compare
...