Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Tree Traversals: Depth-First and Breadth-First

Editorial

One tree, four lists

Almost every tree problem starts by visiting every node once, and the order you visit them in decides what you can work out on the way. Here's one tree, [5, 2, 6, 1, 4, null, 7, null, null, 3], visited four ways:

OrderThe ruleThis treeWhat it's for
Preordera node, then its left subtree, then its right5 2 1 4 3 6 7copying or saving a tree: the root comes first
Inorderthe left subtree, then the node, then the right1 2 3 4 5 6 7a binary search tree comes out sorted
Postorderthe left subtree, then the right, then the node1 3 4 2 7 6 5answers built from the children's answers
Level orderlevel by level, left to right in each5 · 2 6 · 1 4 7 · 3anything measured from the root: views, widths

The first three go as deep as they can before coming back, so they're called depth-first. Level order spreads out from the root one level at a time, which makes it breadth-first. This tree's inorder happens to come out 1 to 7, sorted: it's a binary search tree, the next section's subject. The three depth-first orders look like three algorithms, and they're really one:

The lesson's tree, 5 at the top, with a dashed line walking around its outline counterclockwise from the root. Every node has three marks on the walk: an indigo dot on its left side, an amber dot underneath, a green dot on its right side. Below, three rows: the indigo dots in the order the walk meets them give preorder 5 2 1 4 3 6 7, the amber dots inorder 1 to 7, the green dots postorder 1 3 4 2 7 6 5.

Three places to write a node down

Walk around the outline of the tree, starting down the root's left side and keeping the tree on your left. You pass every node three times: on its left side as you go down, underneath it as you cross from its left subtree to its right, and on its right side as you come back up. Write each node down at its first pass and you get preorder, at the second inorder, at the third postorder.

The recursion is that walk. Calling on the left child is going down the left subtree, the line after it is crossing underneath, and returning is coming up the right side:

// One recursion, three places to write the node down.
void walk(TreeNode* node, vector<int>& pre, vector<int>& in, vector<int>& post) {
    if (node == nullptr) return;
    pre.push_back(node->val);                  // before both subtrees
    walk(node->left, pre, in, post);
    in.push_back(node->val);                   // between them
    walk(node->right, pre, in, post);
    post.push_back(node->val);                 // after both
}

def walk(node, pre, ino, post):
    """One recursion, three places to write the node down."""
    if node is None:
        return
    pre.append(node.val)                       # before both subtrees
    walk(node.left, pre, ino, post)
    ino.append(node.val)                       # between them
    walk(node.right, pre, ino, post)
    post.append(node.val)                      # after both

// One recursion, three places to write the node down.
static void walk(TreeNode node, List<Integer> pre, List<Integer> in, List<Integer> post) {
    if (node == null) return;
    pre.add(node.val);                         // before both subtrees
    walk(node.left, pre, in, post);
    in.add(node.val);                          // between them
    walk(node.right, pre, in, post);
    post.add(node.val);                        // after both
}

// One recursion, three places to write the node down.
function walk(node, pre, ino, post) {
    if (node === null) return;
    pre.push(node.val);                        // before both subtrees
    walk(node.left, pre, ino, post);
    ino.push(node.val);                        // between them
    walk(node.right, pre, ino, post);
    post.push(node.val);                       // after both
}

Each printed [5, 2, 1, 4, 3, 6, 7], [1, 2, 3, 4, 5, 6, 7] and [1, 3, 4, 2, 7, 6, 5]. The only difference between the three orders is which line writes the node: before both calls, between them, or after both. Each visits every node once, O(n) time, with O(h) calls open for a tree of height h. Here is the walk, step by step:

The walk around the outline — Indigo is where the walk is, violet the nodes it has finished; the rows fill as the walk passes each side.

A leaf is passed on all three sides in one go, so it lands in all three lists together. A node with children waits: preorder takes it on the way down, inorder after its left subtree, postorder only after both.

Without recursion: your own stack

The open calls are a stack: each one waits for the call it made to return. You can keep that stack yourself, which is what interviewers mean by "now do it iteratively", and what saves you on a tall tree (Introduction to Binary Trees measured where each language's call stack gives out).

Inorder is the one asked most. Go left as far as you can, pushing every node on the way: each is waiting for its left subtree. When you can't go further, pop: that node's left side is done, so write it, then do the same with its right subtree:

// Inorder without recursion: the stack holds nodes whose left side is still being walked.
vector<int> inorder(TreeNode* root) {
    vector<int> out;
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (node != nullptr || !stack.empty()) {
        while (node != nullptr) {              // go left as far as possible, keeping the path
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back();                   // the deepest node not written yet
        stack.pop_back();
        out.push_back(node->val);
        node = node->right;                    // then its right subtree
    }
    return out;
}

def inorder(root):
    """Inorder without recursion: the stack holds nodes whose left side is still being walked."""
    out, stack, node = [], [], root
    while node or stack:
        while node:                            # go left as far as possible, keeping the path
            stack.append(node)
            node = node.left
        node = stack.pop()                     # the deepest node not written yet
        out.append(node.val)
        node = node.right                      # then its right subtree
    return out

// Inorder without recursion: the stack holds nodes whose left side is still being walked.
static List<Integer> inorder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {                 // go left as far as possible, keeping the path
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();                    // the deepest node not written yet
        out.add(node.val);
        node = node.right;                     // then its right subtree
    }
    return out;
}

// Inorder without recursion: the stack holds nodes whose left side is still being walked.
function inorder(root) {
    const out = [];
    const stack = [];
    let node = root;
    while (node !== null || stack.length) {
        while (node !== null) {                // go left as far as possible, keeping the path
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();                    // the deepest node not written yet
        out.push(node.val);
        node = node.right;                     // then its right subtree
    }
    return out;
}

Each printed [1, 2, 3, 4, 5, 6, 7] for the lesson's tree, then [1, 3, 2], [] and [1] for the problem's examples. Every node is pushed once and popped once, so it's O(n), and the stack never holds more than the tree is tall. Watch the stack:

Inorder with a stack — Amber are the nodes on the stack, waiting for their left side; green is the node just popped and written; violet the nodes already written.

Preorder is simpler: pop a node, write it, and push its right child and then its left, so the left comes off first. Postorder has a neat trick: do preorder with the children pushed the other way round, which writes root, right, left, and reverse the result to get left, right, root:

def preorder(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:                         # right first, so the left comes off the stack first
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out


def postorder(root):
    """Root, right, left, written backwards: 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]

On the lesson's tree they printed [5, 2, 1, 4, 3, 6, 7] and [1, 3, 4, 2, 7, 6, 5], the same lists as the recursion.

Now you walk the tree

Below, pick an order and click the nodes in that order. For the depth-first orders, the open calls are shown as the path from the root; for level order, the queue. A wrong pick is refused with the reason, the node that has to come first lit. Try all four on the same tree, then on a tree of your own.

Walk the Tree: click every node in preorder, inorder, postorder or level order

Level by level, with a queue

Level order can't follow the walk around the outline: it needs the nodes nearest the root first. A queue gives exactly that. Start with the root in it; take the front node, write it, and add its children at the back. Children always join behind everything already waiting, so a level is finished before the next one starts.

Many problems want each level as its own list, and one line does it: at the start of a level, the queue holds exactly that level, so take that many nodes off the front:

// Level order, one list per level: the queue's size at the start of a level is that level.
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    queue<TreeNode*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        vector<int> level;
        for (size_t n = q.size(); n > 0; n--) {   // exactly the nodes of this level
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        levels.push_back(level);
    }
    return levels;
}

from collections import deque


def level_order(root):
    """Level order, one list per level: the queue's size at the start of a level is that level."""
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):            # exactly the nodes of this level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

// Level order, one list per level: the queue's size at the start of a level is that level.
static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        for (int n = queue.size(); n > 0; n--) {  // exactly the nodes of this level
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        levels.add(level);
    }
    return levels;
}

// Level order, one list per level: the queue's size at the start of a level is that level.
function levelOrder(root) {
    const levels = [];
    let queue = root ? [root] : [];
    while (queue.length) {
        const level = [];
        const next = [];                       // the next level, built while this one is read
        for (const node of queue) {
            level.push(node.val);
            if (node.left) next.push(node.left);
            if (node.right) next.push(node.right);
        }
        levels.push(level);
        queue = next;
    }
    return levels;
}

Each printed [[5], [2, 6], [1, 4, 7], [3]], [[3], [9, 20], [15, 7]], [[1]], []: the lesson's tree and the problem's examples. JavaScript builds the next level in its own array instead of shifting a queue (Introduction to Queues measured why a long shift() is slow). Every node joins the queue once: O(n).

Level order with a queue — Amber are the nodes in the queue, indigo the node being written, violet the nodes already written.

The lesson's tree drawn with its levels as horizontal bands, 0 to 3. At the moment level 2 begins, the queue strip under the tree holds exactly 1, 4 and 7, the whole of level 2, while level 3 is still empty in the queue. A bracket over the strip reads: its length is the level.

The obvious way without a queue is to walk the whole tree once per level, keeping the nodes at that depth. That's correct, and it costs a full walk per level, O(n · h). On a tall tree it's quadratic. In Python, on trees with a long right-hand chain and a leaf off every node:

NodesLevelsA walk per levelThe queue
1,00050194.5 ms0.50 ms
2,0001,001376.8 ms0.93 ms
4,0002,0011,509.0 ms1.82 ms
8,0004,0016,094.5 ms3.57 ms

Each doubling made the walks about four times slower, 94 ms to 6,094 ms for eight times the nodes, while the queue stayed in step with n. The queue's cost is memory: it holds a level at a time, and a complete tree's widest level is half its nodes. On a complete tree of a million, the queue reached 500,000 nodes at once, the last level of 475,713 plus the rest of the level above.

Variations on a level

Most level-order problems are the template plus one small change.

Zigzag. Binary Tree Zigzag Level Order Traversal reads the levels left to right, then right to left, alternating. Collect each level as usual and reverse every other one:

def zigzag(root):
    levels = level_order(root)
    return [level if depth % 2 == 0 else level[::-1] for depth, level in enumerate(levels)]

On [3, 9, 20, null, null, 15, 7] it returned [[3], [20, 9], [15, 7]], and on the lesson's tree [[5], [6, 2], [1, 4, 7], [3]].

The right side view. Binary Tree Right Side View asks what you'd see standing to the right of the tree: the last node of every level. A level's last node is right there in the template:

def right_side_view(root):
    return [level[-1] for level in level_order(root)]   # the last node on each level

On [1, 2, 3, null, 5, null, 4] it returned [1, 3, 4], and on the lesson's tree [5, 6, 7, 3]: the 3 shows because nothing on level 3 stands to its right.

The width. Maximum Width of Binary Tree measures each level from its leftmost node to its rightmost, counting the missing places in between as if the tree were complete. Number the places the way the array layout does: if a node is at position p, its children are at 2p + 1 and 2p + 2. A level's width is its last position minus its first, plus one:

The tree 1, 3, 2, 5, 3, null, 9 with a position under each node: 0 for the root, 1 and 2 below it, and 3, 4 and 6 on the bottom level, where place 5 is an empty dashed slot. A bracket across the bottom level reads 6 − 3 + 1 = 4. Each level's positions are also shown counted from that level's first node, starting at 0.
def width_of(root):
    best, queue = 0, deque([(root, 0)] if root else [])
    while queue:
        first = queue[0][1]                    # this level's leftmost position
        for _ in range(len(queue)):
            node, pos = queue.popleft()
            pos -= first                       # count from the level's left end: positions stay small
            if node.left:
                queue.append((node.left, 2 * pos + 1))
            if node.right:
                queue.append((node.right, 2 * pos + 2))
        best = max(best, pos + 1)              # the level's last position, plus one
    return best

It returned 4, 7, 2 on the problem's three examples, and 4 on the lesson's tree. The positions double on every level, so a tall tree reaches positions far past any integer type. Subtracting each level's first position keeps them small, and the width doesn't change, since it's a difference.

Next pointers. Populating Next Right Pointers in Each Node II gives every node a next link to the node on its right on the same level (null at a level's end), and the follow-up asks for O(1) extra space, so no queue. The trick: once a level is linked, you can walk along it through its next links, and while you walk it, link the level below behind a dummy head:

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


def connect(root):
    """Link every level left to right, with no queue: walk each level through the links already made."""
    level = root
    while level:
        dummy = tail = Node(0)                 # the next level's chain grows behind a dummy head
        node = level
        while node:
            for child in (node.left, node.right):
                if child:
                    tail.next = child
                    tail = child
            node = node.next
        level = dummy.next
    return root

On [1, 2, 3, 4, 5, null, 7] the levels read through their links as [1,#,2,3,#,4,5,7,#], LeetCode's way of printing it, and on the lesson's tree as [5,#,2,6,#,1,4,7,#,3,#]. Each node is touched twice, once as a child being linked and once as a parent being walked: O(n) time, O(1) extra space.

Spotting it, and when it breaks

The clues. "Return the preorder / inorder / postorder" is the template itself. "Serialize", "copy" or "clone" a tree: preorder, root first. "In sorted order" or "the k-th smallest" in a binary search tree: inorder. An answer at each node made from its children's answers (heights, sizes, sums, balanced or not): postorder. "Level by level", "each level", "the view from the side", "the width", "the nearest", "the minimum depth": level order.

The near-misses. The minimum depth wants the first leaf by distance, and level order finds it without visiting the whole tree, where a depth-first search has to see every node. Paths from the root to a leaf are depth-first with the path carried down (Recursion on Trees: Heights, Paths and Return Values). Vertical order and the top view need a column for each node as well as its level (Views, Ancestors and Distances). A graph needs a visited set as well: a tree has no cycles, a graph can (Graphs).

When it breaks. Recursion goes as deep as the tree, so a long chain needs the stack versions. A level-order queue holds a whole level, half the tree when it's complete. And positions that double per level outgrow every integer type unless you count from each level's start.

Bugs that cost a submission

Pushing the left child first in iterative preorder.

def preorder(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:                          # wrong: the left goes in first, so it comes off last
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return out

On the lesson's tree it returned [5, 6, 7, 2, 4, 3, 1]; preorder is [5, 2, 1, 4, 3, 6, 7]. A stack hands back the last thing pushed, so the right child has to go in first.

Not snapshotting the level.

def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level, count = [], 0
        while count < len(queue):              # wrong: the length changes as nodes leave and children join
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            count += 1
        levels.append(level)
    return levels

On the lesson's tree it returned [[5, 2, 6], [1, 4], [7], [3]] instead of [[5], [2, 6], [1, 4, 7], [3]]: children joined while the loop was still counting, so levels ran into each other. Read the queue's length once, before the level starts.

Reversing the wrong levels in zigzag.

def zigzag(root):
    levels = level_order(root)
    return [level[::-1] if depth % 2 == 0 else level for depth, level in enumerate(levels)]   # wrong levels

On [3, 9, 20, null, null, 15, 7] it returned [[3], [9, 20], [7, 15]]; the answer is [[3], [20, 9], [15, 7]]. Level 0 reads left to right, so the odd levels are the reversed ones.

Taking each level's first node for the right side view.

def right_side_view(root):
    return [level[0] for level in level_order(root)]    # wrong: the first node on each level

On [1, 2, 3, null, 5, null, 4] it returned [1, 2, 5], the view from the left; the answer is [1, 3, 4].

Positions without the offset, in JavaScript. Maximum width with last = pos - first; computed from raw positions, on a tree whose only wide level is the bottom one, two nodes under a long chain of left children: right up to depth 50, and from depth 60 it returned 1 instead of 2. JavaScript's numbers are exact only up to 2⁵³, and by then 2p + 1 and 2p + 2 round to the same value. Counting each level from its first position gave 2 at every depth. Java and C++ survived this test, because their 64-bit positions wrap round consistently and the difference still comes out right, but C++ signed overflow is undefined behaviour, and LeetCode's C++ build stops the program for it.

Check yourself

Quiz

1 / 6

Multiple choice

What is the postorder of [1, 2, 3, 4, 5]?

Practice problems

In this order:

  1. Binary Tree Traversals: the three depth-first orders on one tree.
  2. Binary Tree Preorder Traversal: root first, then with a stack.
  3. Binary Tree Inorder Traversal: left side first, the stack that goes left.
  4. Binary Tree Postorder Traversal: children first, or root-right-left reversed.
  5. All Three Traversals: one walk, three lists.
  6. Binary Tree Level Order Traversal: the queue and its snapshot.
  7. Binary Tree Zigzag Level Order Traversal: every other level reversed.
  8. Binary Tree Right Side View: the last node of each level.
  9. Maximum Width of Binary Tree: positions, counted from each level's start.
  10. Populating Next Right Pointers in Each Node II: link the levels with no queue.

Next, Recursion on Trees: Heights, Paths and Return Values: what each call hands back to its parent, and the answers built from it.