Topics

Trees: A Study Guide

A tree is a hierarchical structure of nodes with one root and no cycles: every node except the root has exactly one parent. A binary tree limits each node to at most two children (left and right). A binary search tree (BST) adds an ordering invariant: everything in the left subtree is smaller than the node, everything in the right subtree is larger. That invariant is what makes a balanced BST fast to search.

Why Trees Matter#

Trees model anything hierarchical: file systems, DOM documents, decision processes, parse trees. In interviews they are a fixture because recursion feels natural on them, and because a single question (“is this a valid BST?”, “what is the max depth?”) tests whether a candidate can reason about a structure defined in terms of itself. A tree is also the bridge to graphs: a tree is just a connected acyclic graph.

Key Operations and Their Big-O#

For a balanced BST the height is O(log n), which is where the fast bounds come from:

OperationBalanced BSTWorst case (skewed)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
Traverse all nodesO(n)O(n)

The worst case matters: a BST built from already-sorted input degrades into a linked list, so real systems use self-balancing variants (AVL, red-black) covered in the advanced day.

A Short Example#

The three depth-first traversals differ only in when you visit the node relative to its children. In-order traversal of a BST yields sorted values:

 1class Node:
 2    def __init__(self, val, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6
 7def inorder(node, out):
 8    if not node:
 9        return
10    inorder(node.left, out)
11    out.append(node.val)      # visit between the two subtrees
12    inorder(node.right, out)
13    return out

Common Pitfalls#

  • Assuming balance. Big-O for a BST is only O(log n) if it stays balanced. State that assumption out loud.
  • Validating a BST with a local check. Comparing each node only to its immediate children is wrong; you must carry down a valid (low, high) range.
  • Forgetting the null base case. Every recursive tree function needs an if not node: return guard or it crashes on leaves.
  • Recursion depth on deep trees. A degenerate tree can blow Python’s recursion limit; know the iterative stack version of your traversals.

Where the Curriculum Covers This#

In the 60-day challenge: