Trees

No. 06 · SVG · Marble runbinary tree · BST · DFS · BFS · sets and maps

Drag across the board. Click it, then use ← → to step and Space to play.

A tree is a board of gates. The root sits at the top. Every gate (a node) has at most two grooves leading down, to a left child and a right child, and a gate with no grooves below it is a leaf. There are two ways to walk the board. DFS rolls all the way down one path before backing up, and keeps that path on the call stack. BFS clears the board one row (level) at a time, with a queue. In a BST every gate sends smaller values left and larger values right, so a search rolls down a single path.

FIG. 6 · Eleven gates, built by inserting 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7 into a BST. Gates are laid out left to right in sorted order, so a plumb line dropped from each one lands in order. The red marks whatever the code is touching right now. Callouts: A root, B leaf, C depth and height.

Step 1 / 1
READY
Nodes visited
Extra space
Tree
Result
Codemax_depth.py
Code
def max_depth(node):               # DFS: base case, recurse, combine
    if not node:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

Examples

DFS · LeetCode 98

Checking each node against its parent is not enough: every node must fit between bounds set by all its ancestors. DFS passes (lo, hi) down the tree. This tree hides a 6 inside the left subtree of 5. Trigger: "valid BST".

O(n) timeO(h) spaceeach node checked once; the call stack is as deep as the tree
BFS · LeetCode 199

Standing on the right, you see one node per level: the last one. BFS processes the tree level by level, so keep the last node of each level. Trigger: "right side view", "level order".

O(n) timeO(w) spaceeach node enters and leaves the queue once; the queue holds one level (w = widest level)

Time and space

n is the number of nodes, h the height (longest root-to-leaf path), w the width (most nodes on one level). The last column fills in when a run finishes.

OperationTimeSpaceWhyLast run on the bench
DFS (recursive)O(n)O(h)Every node is visited once. The call stack holds one frame per node on the current path.not run yet
BFS (queue)O(n)O(w)Every node is queued and removed once. The queue holds about one level at a time.not run yet
BST search, insert, removeO(log n) balanced · O(n) skewedO(1) iterativeOne comparison per level, so the cost is the height: log n if balanced, n if every node has only one child.not run yet
Inorder traversal · TreeSet / TreeMap iterationO(n)O(h)Left, node, right visits a BST in sorted order. TreeMap get, put and remove are O(log n) because the tree is kept balanced.not run yet

DFS or BFS: which space cost wins?

DFS keeps one root-to-leaf path: O(h). BFS keeps a whole level: O(w). In a balanced tree h ≈ log n but the bottom level holds about n/2 nodes, so DFS uses far less memory. In a long skewed chain it is the reverse: h = n while w = 1.

BST, heap, TreeSet, TreeMap

BST: left smaller, right larger

For every node, everything in its left subtree is smaller and everything in its right subtree is larger. That ordering is what makes search walk one path, and what makes inorder traversal come out sorted.

Heap (min-heap): node smaller than its children

A heap only promises that a parent is smaller than its children, nothing about left vs right. So the minimum is always at the root (O(1) to read, O(log n) to remove), but searching for an arbitrary value is O(n).

TreeSet: a balanced BST of values

Each node holds one value, kept sorted. Add, remove and contains are O(log n), and iterating gives the values in order. Python has no built-in TreeSet: use sortedcontainers.SortedList, or bisect on a sorted list.

TreeMap: a balanced BST of (key, value)

Nodes are ordered by key and carry a value. get, put and remove are O(log n), plus "floor" and "ceiling" lookups that a hash map cannot do. In Python: sortedcontainers.SortedDict.

Trigger words: which walk the problem wants

DFS

  • depth
  • path
  • subtree
  • valid BST

Base case at None, recurse into the children, combine the answers.

BFS

  • level order
  • right side view

A queue, processing one full level per round.

BST or TreeMap

  • sorted keys with inserts and deletes

Keep the data ordered while it keeps changing.

Template

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def max_depth(node):               # DFS: base case, recurse, combine
    if not node:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

from collections import deque
def level_order(root):             # BFS
    q = deque([root] if root else [])
    levels = []
    while q:
        level = []
        for _ in range(len(q)):    # one full level
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels

def bst_search(root, target):      # go left if smaller, right if larger
    while root:
        if target < root.val:
            root = root.left
        elif target > root.val:
            root = root.right
        else:
            return True
    return False