Tree

Trees are one of the most fundamental structures in computer science. They model hierarchies, organize data for efficient search, and provide the recursive structure that makes many algorithms elegant. Before we can solve problems on trees, we need to know how to visit every node systematically. This is the role of tree traversal: a procedure that visits each node in a tree exactly once, in a well-defined order.

Two families of traversal strategies cover essentially all tree problems. Breadth-First Search (BFS) explores the tree level by level, visiting all nodes at depth $d$ before any node at depth $d + 1$. Depth-First Search (DFS) explores as far as possible along each branch before backtracking, and comes in three classical orderings: pre-order, in-order, and post-order.

This article begins with the formal definition of a tree and the key terminology needed to reason about tree problems precisely. We then develop each traversal strategy as both a concept and a code template, and finally organize the main problem patterns that each traversal naturally solves.

What is a Tree?

A tree is a connected, acyclic, undirected graph. In its most general form, a tree with $n$ nodes has exactly $n - 1$ edges, and there is exactly one path between any two nodes. The absence of cycles is what distinguishes a tree from a general graph, and it is precisely this property that allows tree traversals to operate without a visited set: since there is only one path to each node, we can never revisit a node by following edges.

A rooted tree designates one node as the root, which induces a parent-child hierarchy on all edges. Every node except the root has exactly one parent, and the edges point "downward" from parent to child. Most tree problems in practice operate on rooted trees, so the vocabulary below assumes a root is fixed.

The key terminology is concise but essential. A leaf is a node with no children. An internal node has at least one child. The depth of a node is the number of edges on the path from the root to that node, so the root has depth zero. The height of a node is the number of edges on the longest downward path from that node to a leaf, and the height of the tree is the height of the root. A subtree rooted at node $v$ consists of $v$ and all its descendants. Two nodes sharing the same parent are called siblings. A node $u$ is an ancestor of $v$ if $u$ lies on the path from $v$ to the root, and $v$ is a descendant of $u$. The degree of a node is the number of its children, and the level of a node equals its depth.

Understanding these terms precisely matters because tree problems often specify constraints in this vocabulary ("the height of the tree is at most 1000", "return all paths from root to leaf"), and confusion between depth and height or between node and subtree leads to off-by-one errors in both reasoning and code.

Types of Trees

The general rooted tree places no restriction on the number of children per node. In practice, most problems work with more constrained variants, each of which has specific properties that algorithms can exploit.

A binary tree restricts every node to at most two children, conventionally called the left child and the right child. Binary trees are the most common tree type in algorithm design because their two-branch structure maps directly onto binary decisions, enabling clean recursive decomposition.

Within binary trees, several important subtypes arise. A full binary tree (also called a strict or proper binary tree) is one where every node has either zero or two children, never exactly one. A complete binary tree has every level fully filled except possibly the last, which is filled from left to right. Complete binary trees are the structural foundation of binary heaps and can be stored efficiently in an array without pointers, since the parent of node at index $i$ is at index $\lfloor (i-1)/2 \rfloor$ and its children are at indices $2i + 1$ and $2i + 2$. A perfect binary tree is both full and complete: every internal node has exactly two children and all leaves are at the same depth. A perfect binary tree of height $h$ has exactly $2^{h+1} - 1$ nodes.

A balanced binary tree is one where, for every node, the heights of its left and right subtrees differ by at most one. The height of a balanced tree with $n$ nodes is $O(\log n)$, which guarantees efficient operations. Self-balancing binary search trees such as AVL trees and red-black trees maintain this balance invariant automatically through rotations during insertions and deletions.

At the opposite extreme, a degenerate (or skewed) tree is one where every internal node has exactly one child. The tree degenerates into a linked list, and operations that are normally $O(\log n)$ on balanced trees become $O(n)$. Recognizing when a tree might be degenerate is important for worst-case complexity analysis.

Beyond binary trees, an N-ary tree (also called a k-ary or m-ary tree) allows each node to have any number of children. File systems, organizational hierarchies, and tries are all examples of N-ary trees. The traversal algorithms presented in this article generalize to N-ary trees by iterating over all children rather than just left and right.

For taxonomy completeness, B-trees are a family of self-balancing search trees designed for disk-based storage, where each node can contain multiple keys and have many children. They are essential in database indexing but rarely appear in algorithm design exercises.

The interactive visualization below illustrates the main tree types described above.

One important observation ties this article to its sequel: every tree is a graph, specifically a connected acyclic undirected graph. The tree traversal techniques developed here are therefore special cases of the graph traversal techniques presented later. The key simplification that trees enjoy is the absence of cycles, which means tree traversals do not need a visited set.

For all the examples in this article, consider the following TreeNode structure.

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

BFS: Level-Order Traversal

BFS on trees processes nodes level by level, starting from the root and moving down to each subsequent depth. The mechanism is a queue: dequeue a node, process it, enqueue its children. Because the queue is FIFO, all nodes at depth $d$ are processed before any node at depth $d + 1$.

Template

The standard BFS template captures the queue length at the start of each level and processes exactly that many nodes. This level-boundary technique is the foundation for virtually all BFS-based tree problems.

function bfsLevelOrder(root: TreeNode | null): number[][] {
    if (!root) {
        return [];
    }

    const result: number[][] = [];
    const queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel: number[] = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            currentLevel.push(node.val);

            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }

        result.push(currentLevel);
    }

    return result;
}

Unlike graph BFS, tree BFS does not need a visited set. The tree structure guarantees that each node appears in the queue exactly once, because there is exactly one path from the root to any node.

Level-based reasoning

The level-boundary technique opens up a family of problems where the answer depends on the structure of individual levels.

The right-side view of a binary tree asks for the last node visible at each level when viewing the tree from the right. This is simply the last node processed in each level of the BFS. The same logic, adapted to pick the first node, gives the left-side view.

Zigzag traversal alternates the direction at each level: left-to-right on even levels, right-to-left on odd levels. The BFS proceeds normally, but the level array is reversed on alternate levels before being appended to the result.

The maximum width of a binary tree measures the largest number of positions between the leftmost and rightmost nodes at any level, including null positions between them. BFS tracks index positions alongside nodes: the root has index 0, and the children of a node at index $i$ have indices $2i + 1$ and $2i + 2$. The width of a level is the difference between the last and first index plus one. To avoid integer overflow in deep trees, the indices can be offset relative to the first index at each level.

Connecting next right pointers asks you to link each node to its immediate right neighbor at the same level. BFS processes the level left-to-right, and each node's next pointer is set to the next node in the level queue. The last node in each level points to null.

All these problems share the same BFS skeleton. The variation lies in what information is extracted from each level: the last element, the reversed order, the index range, or the neighbor linkage.

DFS: Pre-Order, In-Order, and Post-Order

DFS on trees follows each branch as deep as possible before backtracking. The three classical DFS orderings differ in when the root is processed relative to its subtrees. Pre-order processes the root first, then the left subtree, then the right subtree. In-order processes the left subtree, then the root, then the right subtree. Post-order processes the left subtree, then the right subtree, then the root last.

Each ordering is not merely a mechanical variation. The choice of when to process the root determines what information is available at processing time, and this determines which problem families each ordering naturally solves.

Pre-order template

Pre-order processes the root before recursing into children. This means the root's information is available to pass down into the recursive calls, making pre-order the natural fit for problems that propagate information from ancestors to descendants.

function preorderRecursive(root: TreeNode | null): number[] {
    const result: number[] = [];

    function dfs(node: TreeNode | null): void {
        if (!node) {
            return;
        }

        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }

    dfs(root);
    return result;
}

The iterative version uses an explicit stack, pushing the right child before the left so that the left child is processed first (LIFO order).

function preorderIterative(root: TreeNode | null): number[] {
    if (!root) {
        return [];
    }

    const stack: TreeNode[] = [root];
    const result: number[] = [];

    while (stack.length > 0) {
        const node = stack.pop()!;
        result.push(node.val);

        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }

    return result;
}

In-order template

In-order processes the root between the left and right subtrees. For binary search trees, this produces values in sorted ascending order, because the BST invariant guarantees that all left-subtree values are smaller than the root and all right-subtree values are larger.

function inorderRecursive(root: TreeNode | null): number[] {
    const result: number[] = [];

    function dfs(node: TreeNode | null): void {
        if (!node) {
            return;
        }

        dfs(node.left);
        result.push(node.val);
        dfs(node.right);
    }

    dfs(root);
    return result;
}

The iterative in-order traversal is subtler than pre-order because the root must be delayed until the entire left subtree is processed. The standard technique pushes all left children onto the stack until reaching a null, then pops and processes.

function inorderIterative(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let current: TreeNode | null = root;

    while (current || stack.length > 0) {
        while (current) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop()!;
        result.push(current.val);
        current = current.right;
    }

    return result;
}

Post-order template

Post-order processes the root after both subtrees have been fully processed. This means the results of both children are available when the root is finally visited, making post-order the natural fit for problems that aggregate information from descendants.

function postorderRecursive(root: TreeNode | null): number[] {
    const result: number[] = [];

    function dfs(node: TreeNode | null): void {
        if (!node) {
            return;
        }

        dfs(node.left);
        dfs(node.right);
        result.push(node.val);
    }

    dfs(root);
    return result;
}

The iterative post-order can be implemented with two stacks. The first stack drives the traversal, pushing nodes onto the second stack in reverse post-order. Popping the second stack then yields nodes in correct post-order.

function postorderIterative(root: TreeNode | null): number[] {
    if (!root) {
        return [];
    }

    const stack1: TreeNode[] = [root];
    const stack2: TreeNode[] = [];
    const result: number[] = [];

    while (stack1.length > 0) {
        const node = stack1.pop()!;
        stack2.push(node);

        if (node.left) {
            stack1.push(node.left);
        }
        if (node.right) {
            stack1.push(node.right);
        }
    }

    while (stack2.length > 0) {
        result.push(stack2.pop()!.val);
    }

    return result;
}

DFS Problem Patterns

The three DFS orderings are not just traversal mechanisms. They define families of problem patterns based on the direction of information flow in the tree. Understanding which ordering fits which pattern is the key to solving tree problems efficiently.

Path problems (pre-order)

Path problems ask about properties of paths from the root (or an ancestor) to descendants. Because pre-order visits the root before its children, it can carry accumulated state downward through the recursive calls: the current path, the running sum, the minimum or maximum value seen so far.

The simplest example is enumerating all root-to-leaf paths. Pre-order builds the path string incrementally as it descends, appends the result when a leaf is reached, and the call stack naturally handles backtracking.

A more sophisticated variant is Path Sum III, which asks for the count of paths that sum to a target value, where paths can start and end at any node. The standard approach combines pre-order traversal with a prefix sum hash map: at each node, the running sum from the root is maintained, and the number of times (runningSum - target) has been seen as a prefix sum tells you how many valid paths end at the current node.

The maximum difference between a node and its ancestor follows the same pattern. Pre-order tracks the minimum and maximum values seen along the path from the root. At each node, the candidate answer is the maximum of |node.val - minSoFar| and |node.val - maxSoFar|.

Structural comparison (pre-order)

Structural comparison problems ask whether two trees (or two subtrees) share the same shape and values. Pre-order is the natural choice because it processes corresponding nodes in lockstep: both roots first, then both left children, then both right children.

Checking whether two trees are the same tree is a pre-order comparison: if both nodes are null, they match. If one is null and the other is not, they differ. If both exist, compare values and recurse on children.

Checking whether a tree is symmetric is the mirror-image variant: instead of comparing left-with-left and right-with-right, you compare the left child of one subtree with the right child of the other.

Tree construction and reconstruction (pre-order)

Construction problems build a tree from a specification, typically a sorted array or a pair of traversal orders. Pre-order is the natural ordering for construction because it processes the root first, which determines the split point for the subtrees.

Constructing a BST from a sorted array uses pre-order DFS that picks the middle element as the root, then recurses on the left and right halves. This produces a balanced BST with height $O(\log n)$.

Reconstructing a binary tree from pre-order and in-order sequences relies on the fact that the first element of the pre-order sequence is the root. Finding that root in the in-order sequence splits the in-order array into left and right subtrees. The sizes of those subtrees determine how to split the pre-order sequence as well. Using a hash map for the in-order index lookup reduces the overall time from $O(n^2)$ to $O(n)$.

The analogous problem using in-order and post-order sequences works similarly, but the root is the last element of the post-order sequence, and the construction proceeds from right to left.

Subtree analysis (post-order)

Subtree analysis problems compute a property of the tree that depends on information aggregated from children. Post-order is the natural fit because it processes both children before the parent, so the parent has access to the children's computed results.

The diameter of a binary tree (the longest path between any two nodes, measured in edges) is a canonical post-order problem. At each node, the diameter candidate passing through that node is the sum of the heights of its left and right subtrees. The post-order DFS computes heights bottom-up, updating a global maximum diameter as it goes.

The binary tree maximum path sum generalizes the diameter idea to weighted paths. At each node, the maximum path sum through that node is node.val + max(0, leftGain) + max(0, rightGain), where gains are clamped to zero because a negative subtree is better excluded. The value returned upward for the parent to use is node.val + max(0, max(leftGain, rightGain)), because a path through the parent can only extend through one child, not both.

Inverting a binary tree swaps the left and right children of every node. Post-order inverts both subtrees first, then swaps them at the current node. Pre-order works equally well for this problem (swap first, then recurse on the now-swapped children), but the post-order perspective emphasizes that the result of each subtree inversion is fully computed before the parent acts on it.

Finding duplicate subtrees requires serializing each subtree and checking for duplicates. Post-order serialization is the natural choice because each subtree's serialization is complete before it is needed by the parent. A hash map from serialization strings to node references identifies duplicates in $O(n)$ time.

Deleting nodes and returning a forest is a post-order problem where nodes marked for deletion are removed, and their children (if any) become new roots. Post-order ensures that children are processed before their parent, so by the time a node is considered for deletion, its subtrees have already been correctly pruned and potentially promoted to roots.

The distribute coins problem asks for the minimum number of moves to balance coins across a tree so that each node has exactly one. Post-order computes the excess (or deficit) of coins at each subtree. The number of moves through each edge equals the absolute value of the excess flowing through it, and the total is the sum across all edges.

The lowest common ancestor (LCA) of two nodes is found by post-order DFS that returns whether each subtree contains either target node. If a node's left subtree contains one target and its right subtree contains the other, that node is the LCA. If the node itself is one of the targets and one subtree contains the other, the node itself is the LCA.

BST-specific patterns (in-order)

In-order traversal visits BST nodes in sorted order. This property transforms many BST problems into problems on sorted sequences.

Validating a BST checks that the in-order traversal produces a strictly increasing sequence. The standard recursive approach passes down lower and upper bounds: the left child must be less than the current node, and the right child must be greater. An iterative in-order traversal that simply checks each value against the previous one is an equally clean alternative.

Finding the kth smallest element performs an in-order traversal and counts nodes. When the count reaches $k$, the current node is the answer. The iterative in-order template is particularly convenient here because it can be stopped early.

Computing the minimum absolute difference between BST nodes leverages the sorted-order property: consecutive elements in the in-order sequence are the closest pair candidates, so a single in-order traversal tracking the previous value suffices.

A BST iterator that supports next() and hasNext() operations is essentially a controlled in-order traversal. The iterative in-order template provides exactly this: the stack holds the state of the traversal, and each call to next() advances by one step. This provides $O(h)$ space and amortized $O(1)$ time per call.

Serialization and hybrid traversals

Serializing and deserializing a binary tree encodes a tree as a string and reconstructs it. Pre-order DFS is the standard approach: serialize each node's value followed by its children, using a sentinel (like "#") for null nodes. Deserialization reads the pre-order sequence and rebuilds the tree recursively. The sentinel values tell the deserializer when to stop recursing into a subtree and return null.

Flattening a binary tree to a linked list in pre-order requires rearranging the tree's pointers. The post-order approach processes subtrees first, then stitches them together: flatten the left subtree, flatten the right subtree, attach the flattened left subtree as the right child, and append the flattened right subtree at the end of the flattened left. A reverse pre-order approach (right, left, root) can achieve this more elegantly using a global pointer.

Counting nodes in a complete binary tree exploits the completeness property for an $O(\log^2 n)$ algorithm. Pre-order DFS at each node computes the left height and right height. If they are equal, the subtree is a perfect binary tree with $2^h - 1$ nodes. If they differ, recurse on both children. The completeness guarantee ensures that at each level of recursion, at least one subtree is perfect, yielding $O(\log n)$ recursive calls, each taking $O(\log n)$ for the height computation.

Choosing Between BFS and DFS

BFS and DFS are both complete traversal strategies: they visit every node in the tree exactly once. The choice between them depends on the direction of information flow and the nature of the question being asked.

BFS is the right choice when level structure matters. Any problem that asks about the width of the tree, the rightmost (or leftmost) node at each level, zigzag ordering, or connections between nodes at the same depth is naturally a BFS problem. The level-boundary technique gives direct access to the set of nodes at each depth.

DFS is the right choice for recursive structural analysis. Problems that require computing properties of subtrees (height, diameter, balance), propagating information from root to leaves (path sums, value ranges), or building/reconstructing trees from specifications are naturally recursive, and DFS matches the recursive structure of the tree itself.

Memory considerations differ between the two. BFS stores the entire frontier in a queue. For a balanced tree, the widest level has $O(n/2)$ nodes at the leaves, so BFS uses $O(n)$ space in the worst case. DFS (recursive or iterative with a stack) stores at most $O(h)$ nodes, where $h$ is the height. For a balanced tree, $h = O(\log n)$, so DFS is significantly more memory-efficient. For a degenerate tree, $h = O(n)$, and both strategies use comparable space.

Recursive DFS and the call stack. Recursive DFS relies on the language's call stack for backtracking. This is elegant and concise, but deep trees can cause a stack overflow. The iterative DFS template replaces the call stack with an explicit stack data structure, which avoids stack overflow at the cost of slightly more verbose code. In practice, the recursive version is preferred when the tree depth is bounded (e.g., balanced trees, trees with height up to $10^4$), and the iterative version is used when the depth could be very large.

Time and Space Complexity

Every traversal visits each of the $n$ nodes exactly once and performs a constant amount of work per node, giving $O(n)$ time across all strategies. The space complexity depends on the tree's shape, specifically on its height $h$ and its maximum width $w$.

For a balanced binary tree, $h = O(\log n)$ and $w = O(n/2) = O(n)$ (the last level can hold up to half the nodes). For a degenerate (skewed) tree, $h = O(n)$ and $w = O(1)$ (each level has exactly one node). These extremes determine the best and worst cases for each strategy.

The height $h$ is at most $n$ (degenerate case) and at least $\lfloor \log_2 n \rfloor$ (perfect binary tree case). For problems on balanced trees, DFS is strictly more space-efficient than BFS. For problems on arbitrary trees, the worst-case space is $O(n)$ for both strategies, but they hit this worst case on opposite tree shapes: BFS on wide, shallow trees (balanced), DFS on deep, narrow trees (degenerate).

Exercises