Visualizer › Trees
Binary Search Tree Search
In a BST every key on the left is smaller and every key on the right is bigger, so each comparison discards one subtree.
How it works
- O(log n) when the tree is balanced.
- A tree built from sorted input becomes a "linked list" — O(n).
- Self-balancing trees (AVL, Red-Black) keep it O(log n).
Complexity
- Best time: O(1)
- Average time: O(log n)
- Worst time: O(n)
- Extra space: O(1)
Code (Python)
def search(node, target):
while node:
if target == node.val:
return node
node = node.left if target < node.val else node.right
return NonePractise: Trees problems