Searching and Traversal in BST
Explore how to perform searching and traversal in binary search trees (BSTs) using C#. Learn both recursive and iterative approaches, understand BST properties, and grasp why balanced trees enable faster search operations. This lesson helps you build efficient search functions reflecting BST logic and analyze their time complexity.
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. ...