Tree Basics and Traversals

Intuition

A tree is a connected undirected graph without cycles. The following are equivalent ways to recognize one with n vertices: connected with n - 1 edges; acyclic with n - 1 edges; exactly one simple path between any two vertices; every edge is a bridge. That unique path is what makes trees so pleasant: there is never a choice of route, so many questions reduce to one traversal.

Choosing a root turns the tree into a hierarchy:

• the parent of v is the next vertex on the path from v to the root; the root has none;
• children, siblings, ancestors (vertices on the path to the root) and descendants follow;
• depth of v = number of edges from the root; height of the tree = maximum depth;
• the subtree of v = v plus all its descendants;
• a leaf has no children (in an unrooted tree, degree at most 1; "at most" because a single-vertex tree has a degree-0 leaf).

Binary-tree words used in interviews: a full binary tree has 0 or 2 children everywhere; a complete one fills every level except possibly the last, which is filled from the left; a perfect one has all leaves at the same depth. Textbooks disagree on these names, so define them when you use them.

When to use it in interviews / OAs

• The input is n vertices and n - 1 edges (or a parent array): root it, then compute depths, subtree sizes or sums.
• A TreeNode with left and right: almost every question is one of the four traversals with some bookkeeping.
• "Level by level", "right side view", "zigzag", "average of each level": BFS with one loop per level.
• "Is u an ancestor of v" asked many times: entry/exit indices from one DFS.
• Rebuilding a tree from two traversal sequences.

Template

Rooting a tree given as edges

An explicit stack yields a preorder in which every parent comes before its children, so the reversed order visits children first. That gives bottom-up computations (subtree sizes, sums, DP) with no recursion at all.

import sys
from collections import deque
from dataclasses import dataclass


def root_tree(n: int, edges: list[tuple[int, int]], root: int = 0):
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    parent, depth, order = [-1] * n, [0] * n, []
    stack = [root]
    while stack:
        u = stack.pop()
        order.append(u)  # preorder: a parent always precedes its children
        for v in adj[u]:
            if v != parent[u]:  # the only neighbor that is not a child
                parent[v] = u
                depth[v] = depth[u] + 1
                stack.append(v)
    return parent, depth, order


def subtree_sizes(parent: list[int], order: list[int]) -> list[int]:
    size = [1] * len(parent)
    for v in reversed(order):  # children before parents
        if parent[v] != -1:
            size[parent[v]] += size[v]
    return size


def ancestor_checker(parent: list[int], order: list[int]):
    # each subtree is a contiguous block of the preorder
    size = subtree_sizes(parent, order)
    tin = [0] * len(order)
    for i, v in enumerate(order):
        tin[v] = i

    def is_ancestor(u: int, v: int) -> bool:  # True also when u == v
        return tin[u] <= tin[v] < tin[u] + size[u]

    return is_ancestor

Binary tree traversals

@dataclass
class TreeNode:
    val: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


def inorder_iter(root: TreeNode | None) -> list[int]:
    out, stack, node = [], [], root
    while stack or node:
        while node:  # walk left as far as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out


def preorder_iter(root: TreeNode | None) -> list[int]:
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:  # push right first so left is processed first
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out


def postorder_iter(root: TreeNode | None) -> list[int]:
    # root-right-left preorder, reversed, is left-right-root
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return out[::-1]


def level_order(root: TreeNode | None) -> list[list[int]]:
    levels, q = [], deque([root] if root else [])
    while q:
        levels.append([])
        for _ in range(len(q)):  # exactly the nodes of the current level
            node = q.popleft()
            levels[-1].append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return levels

Rebuilding from preorder and inorder

The first preorder value is the root; its position in the inorder splits the left and right subtrees. A value-to-index map makes each split O(1). Values must be distinct.

def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    sys.setrecursionlimit(max(1000, 2 * len(preorder) + 50))
    pos = {v: i for i, v in enumerate(inorder)}
    it = iter(preorder)

    def build(lo: int, hi: int) -> TreeNode | None:  # inorder[lo:hi]
        if lo >= hi:
            return None
        node = TreeNode(next(it))
        mid = pos[node.val]
        node.left = build(lo, mid)  # left subtree consumes the next preorder values
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(inorder))

Complexity

Rooting, subtree sizes, every traversal and the rebuild are O(n) time. Extra space is O(n) for adjacency and order, or O(h) for the stacks of binary-tree traversals, where h is the height (h = n for a skewed tree). After the O(n) preprocessing, each ancestor query is O(1).

Common pitfalls

• Forgetting the parent check in an undirected adjacency list: the traversal walks back up and loops forever (or double counts).
• Recursion depth. A skewed tree with 10^4 nodes breaks Python's default limit of about 1000 frames. Use the iterative forms, or raise the limit as build_tree does.
• n = 1. No edges at all; the single vertex is both root and leaf. Many "leaf" or "center" algorithms special-case it.
• Depth vs. height. Depth is measured from the root down to a node; height is measured from a node down to its deepest leaf. Agree on edges vs. nodes too.
• Duplicate values break the preorder + inorder rebuild, since the split position becomes ambiguous.
• Level-order without freezing the level size. Read len(q) before the inner loop; it changes as children are appended.

Interview variations

• Bottom-up DP in reverse order. Subtree sums, "count nodes whose value equals the subtree average", "minimum cameras", "distribute coins": compute children before parents.
• Rerooting. "Sum of distances from every node": one bottom-up pass for subtree sizes, one top-down pass that moves the root across each edge.
• Distance-K nodes in a binary tree. Add parent pointers (one traversal), then BFS from the target as in a general graph.
• Serialize / deserialize. Preorder with null markers is enough to rebuild a binary tree uniquely.
• Side views and zigzag. Level-order with a per-level rule (last element, alternate direction).
• Morris traversal. Inorder in O(1) extra space by temporarily threading right pointers; rarely required, good to mention.
• Other rebuilds. Inorder + postorder works like the template from the back; preorder + postorder only determines a full binary tree.