Searching and Traversal in BST
Explore searching and traversal methods in binary search trees (BST). Understand how BST ordering optimizes search operations, learn recursive and iterative search implementations in JavaScript, and grasp why balanced BSTs provide fast search times. Gain practical insights into time complexity and efficient algorithm design for BST traversal.
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
null, 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
...