Lesson 9 / 42

Binary Tree

Each node has up to two children; traversals visit every node once.

Shape & terms

        1
       / \
      2   3
     / \
    4   5

Root at top, leaves at bottom. Height is the longest root-to-leaf path. A balanced tree has height ~log n; a degenerate one is a linked list with height n.

The four traversals

Depth-first: pre/in/post-order differ only by when you visit the node vs. recurse. Breadth-first uses a queue, level by level.

def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)     # visit between children
    inorder(node.right, out)

from collections import deque
def bfs(root):
    q, out = deque([root]), []
    while q:
        n = q.popleft()
        out.append(n.val)
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)
    return out

Org chart

The CEO is the root; each manager has reports beneath them. To brief everyone you can go department-deep (DFS) or floor-by-floor (BFS).

Interview pattern

Most tree problems are one recursive function returning info from children (height, sum, is-balanced, LCA). Think: "what do I need from left and right to answer for this node?"