Trees & Binary Search Trees
Recursion as a tool, traversals (preorder/inorder/postorder), and the BST invariant.
Trees, conceptually
A tree is a hierarchical structure: a root node with children, each of which can have children of its own. Unlike linked lists, trees branch. Real-world examples: the file system, HTML/DOM, organizational charts, the decision tree of an AI.
A BINARY tree restricts each node to at most two children, conventionally called `left` and `right`. The natural way to implement it is recursive — a node, with two pointers.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))Recursion: the natural language of trees
Almost every tree algorithm follows the same shape: handle the empty case (the base case), do something with the current node, then recurse on the children. If you find yourself fighting trees, it's almost always because you're not letting recursion do its job.
# Count all nodes
def count(root):
if not root:
return 0
return 1 + count(root.left) + count(root.right)
# Maximum depth
def depth(root):
if not root:
return 0
return 1 + max(depth(root.left), depth(root.right))
print(count(root), depth(root))The four traversals
- Preorder — root, then left subtree, then right. Used to copy or serialize a tree.
- Inorder — left subtree, root, right. On a BST, this visits nodes in sorted order.
- Postorder — left, right, then root. Used when children must be processed before the parent (e.g. computing a checksum).
- Level-order (BFS) — visit by depth, using a queue. Used for shortest-path problems and \"by row\" outputs.
def inorder(root, out=None):
if out is None:
out = []
if not root:
return out
inorder(root.left, out)
out.append(root.val)
inorder(root.right, out)
return out
from collections import deque
def level_order(root):
if not root: return []
q, out = deque([root]), []
while q:
node = q.popleft()
out.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return outBinary Search Tree (BST)
A BST adds an invariant: for every node, all values in the LEFT subtree are smaller, and all values in the RIGHT subtree are larger. That single rule turns search, insertion, and deletion into O(log n) operations — IF the tree is balanced.
def bst_insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
elif val > root.val:
root.right = bst_insert(root.right, val)
return root
def bst_contains(root, val):
if not root: return False
if val == root.val: return True
if val < root.val: return bst_contains(root.left, val)
return bst_contains(root.right, val)