BST search
- Algorithms course
- Intermediate
- Lesson 31/80
- 4 min
Search a value in O(log n) average.
BST search
Search in a BST follows binary-search logic. If the target is smaller than the root look in the left subtree, if larger look right. If we reach None the value is not present.
Each step halves the search space; a balanced BST gives O(log n). This is the same logic as binary search on a sorted array.
The BST advantage: insertion and deletion are equally fast; more flexible than an array.
Search cost
In a balanced BST search is O(log n) because each step halves the search space. This matches binary search on a sorted array.
But an unbalanced BST (e.g. inserting sorted data) becomes chain-like and search degrades to O(n). This is why balancing matters.
AVL or red-black trees provide automatic balance so search stays O(log n) always.
Practice BST search
Write search(node, target). Smaller left, larger right, equal True, None False. Print True with root = Node(5); root.left = Node(3); print(search(root, 3)).
Starter code
def search(node, target):
# Search in BSTSample solution
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def search(node, target):
# Search in BST
if node is None:
return False
if node.val == target:
return True
if target < node.val:
return search(node.left, target)
return search(node.right, target)
root = Node(5)
root.left = Node(3)
print(search(root, 3))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 BST search: match the terms
| Term | Meaning |
|---|---|
Smaller |
Left |
Larger |
Right |
Equal |
Found |
None |
Absent |
2 Search cost in an unbalanced BST?
- O(1)
- O(n^2)
- O(log n)
- O(n) Correct answer
Explanation: O(n)
3 Found
if node.val == target: return ____if node.val == target: return TrueExplanation: True is right.