Binary Search Trees
BST property, searching, and why BSTs are useful. Understand the ordering invariant that makes BSTs efficient.
A Binary Search Tree (BST) is a binary tree with a special ordering property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property enables efficient searching, insertion, and deletion.
The BST Property
For every node with value x:
- All nodes in the left subtree have values < x
- All nodes in the right subtree have values > x
Valid BST: Not a BST:
8 8
/ \ / \
3 10 3 10
/ \ \ / \ \
1 6 14 1 9 14 <- 9 > 8 but in left subtree
/ \ / / \ /
4 7 13 4 7 13
Why BSTs?
The ordering property allows binary search in a tree structure:
- Search: O(log n) average, O(n) worst
- Insert: O(log n) average, O(n) worst
- Delete: O(log n) average, O(n) worst
Compare to: | Data Structure | Search | Insert | Delete | |----------------|--------|--------|--------| | Sorted Array | O(log n) | O(n) | O(n) | | Linked List | O(n) | O(1) | O(1) | | Hash Table | O(1) | O(1) | O(1) | | BST (balanced) | O(log n) | O(log n) | O(log n) |
BSTs maintain sorted order while allowing efficient insertion and deletion.
Node Structure
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
Searching
Follow the BST property to navigate:
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if node is None:
return None
if val == node.val:
return node
elif val < node.val:
return self._search(node.left, val)
else:
return self._search(node.right, val)
Searching for 6 in BST:
8
/ \
3 10
/ \ \
1 6 14
/ \
4 7
Step 1: 6 < 8, go left
Step 2: 6 > 3, go right
Step 3: 6 == 6, found!
Iterative version:
def search_iterative(self, val):
node = self.root
while node:
if val == node.val:
return node
elif val < node.val:
node = node.left
else:
node = node.right
return None
Finding Minimum and Maximum
Minimum: leftmost node. Maximum: rightmost node.
def find_min(self):
if not self.root:
return None
node = self.root
while node.left:
node = node.left
return node.val
def find_max(self):
if not self.root:
return None
node = self.root
while node.right:
node = node.right
return node.val
Inorder Traversal is Sorted
An inorder traversal of a BST visits nodes in sorted order. This property is useful for validating BSTs and finding the k-th smallest element.
Validating a BST
A tree is a valid BST if inorder traversal produces sorted values:
def is_valid_bst(root):
def validate(node, min_val, max_val):
if node is None:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
Or using inorder traversal:
def is_valid_bst_inorder(root):
prev = float('-inf')
def inorder(node):
nonlocal prev
if node is None:
return True
if not inorder(node.left):
return False
if node.val <= prev:
return False
prev = node.val
return inorder(node.right)
return inorder(root)
Successor and Predecessor
Successor: Next larger value Predecessor: Previous smaller value
def successor(root, val):
"""Find smallest value greater than val."""
successor = None
node = root
while node:
if val < node.val:
successor = node
node = node.left
else:
node = node.right
return successor.val if successor else None
def predecessor(root, val):
"""Find largest value smaller than val."""
predecessor = None
node = root
while node:
if val > node.val:
predecessor = node
node = node.right
else:
node = node.left
return predecessor.val if predecessor else None
Floor and Ceiling
Floor: Largest value ≤ key Ceiling: Smallest value ≥ key
def floor(root, key):
"""Largest value <= key."""
result = None
node = root
while node:
if key == node.val:
return node.val
elif key < node.val:
node = node.left
else:
result = node.val
node = node.right
return result
def ceiling(root, key):
"""Smallest value >= key."""
result = None
node = root
while node:
if key == node.val:
return node.val
elif key > node.val:
node = node.right
else:
result = node.val
node = node.left
return result
Time Complexity
| Operation | Average | Worst (Skewed) | |-----------|---------|----------------| | Search | O(log n) | O(n) | | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) | | Min/Max | O(log n) | O(n) |
Worst Case: Skewed Trees
If you insert sorted data into a BST, it becomes a linked list with O(n) operations. Self-balancing trees (AVL, Red-Black) guarantee O(log n) by maintaining balance.
Balanced vs Unbalanced
Balanced BST (height 2): Skewed BST (height 4):
4 1
/ \ \
2 6 2
/ \ / \ \
1 3 5 7 3
\
4
\
5
Search for 5: 3 steps Search for 5: 5 steps
Range Queries
Find all values in range [low, high]:
def range_query(root, low, high):
result = []
def inorder(node):
if node is None:
return
if node.val > low:
inorder(node.left)
if low <= node.val <= high:
result.append(node.val)
if node.val < high:
inorder(node.right)
inorder(root)
return result
k-th Smallest Element
def kth_smallest(root, k):
count = 0
result = None
def inorder(node):
nonlocal count, result
if node is None or result is not None:
return
inorder(node.left)
count += 1
if count == k:
result = node.val
return
inorder(node.right)
inorder(root)
return result
Applications
- Database indexes: Fast range queries
- Symbol tables: Compiler symbol lookup
- File systems: Directory organization
- Autocomplete: Prefix-based searching
- Scheduling: Priority management
Key Takeaways
- BST property: left < node < right
- Enables O(log n) search, insert, delete when balanced
- Inorder traversal yields sorted order
- Skewed trees degrade to O(n) performance
- Self-balancing variants (AVL, Red-Black) maintain O(log n)
- Supports efficient range queries and ordered operations
BSTs are fundamental for maintaining sorted data dynamically. Understanding their properties and limitations prepares you for more advanced tree structures and database indexing concepts.