Trees model hierarchical relationships — file systems, org charts, DOM structures — and binary search trees specifically add an ordering property that makes searching genuinely efficient.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def search(root, value):
if root is None or root.value == value:
return root
if value < root.value:
return search(root.left, value)
return search(root.right, value)
The Balance Problem
A BST’s search is O(log n) only if the tree stays reasonably balanced — inserting already-sorted data into a naive BST as shown above degrades it into essentially a linked list, O(n) search, defeating the whole point. This is exactly why self-balancing variants exist: AVL trees and Red-Black trees automatically rebalance during insertion, guaranteeing O(log n) regardless of insertion order — and it’s what most language standard library “sorted map” implementations actually use underneath.