A Binary Search Tree stores values so that every node's left subtree contains only smaller values and every right subtree contains only larger values. Search starts at the root and at each node makes one comparison: go left if target is smaller, right if larger, or return found if equal. In a balanced BST this takes O(log n) time.
Example: Find 6 in a BST.
When to use this
→Ordered key-value lookup (database indexes use B-trees, a generalization)
→Range queries — find all values between A and B
→Floor/ceiling operations — find the largest value ≤ target
→Auto-complete / prefix search with tries (a BST variant)
BST search exploits the BST property: every left child is smaller than its parent, every right child is larger. Each comparison lets us eliminate an entire subtree.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
defbst_search(node,target):
2
ifnodeisNone:returnNone
3
iftarget==node.val:returnnode
4
iftarget<node.val:
5
returnbst_search(node.left,target)
6
else:
7
returnbst_search(node.right,target)
8
returnNone
Quick check
What is the time complexity of BST search in a balanced tree?
What is the worst-case time complexity of BST search?