Binary tree traversals: DFS orders and BFS

To traverse a binary tree is to visit every node exactly once, in an order fixed in advance. The depth-first orders follow one branch to the bottom before backing up, and they differ only in when they visit a node: preorder visits it before its two subtrees, inorder between them and postorder after both. Level order is the breadth-first order: it takes the tree one level at a time, from the root down and from left to right, with a queue. Each of the four takes O(n) time for n nodes. A recursive depth-first walk keeps one call open for each node on the path it is on, O(h) memory for a tree of height h, while level order holds up to a whole level in its queue. The order decides what a program can do: copy a tree, list a search tree’s keys in sorted order, add up sizes from the leaves, or reach the nodes closest to the root first.

Four orders on one tree

Each depth-first order is one rule applied at every node, so a single line of the rule produces the whole sequence:

On this tree, and where each order is used:

• Preorder: M E B H G S P R W. Copying a tree, writing it out to rebuild later, and prefix notation.
• Inorder: B E G H M P R S W. A binary search tree’s keys in sorted order.
• Postorder: B G H E R P W S M. Sizes and heights, deleting a tree, and evaluating an expression.
• Level order: M E S B H P W G R. The nodes nearest the root first, and printing by levels.

The code, and what it costs

The three recursive functions below differ only in where the line that records the node sits; preorder also counts how many calls are open at once. Level order takes nodes from the front of a collections.deque and adds their children at the back, which keeps every level ahead of the next. The same program then stores (7 − 2) × (3 + 1) as a tree and walks it:

"""The four traversal orders of one binary tree, and what each order is good for."""
from collections import deque


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


# The lesson's tree: M at the root, E and S below it, and so on down to G and R.
tree = Node("M",
            Node("E", Node("B"), Node("H", Node("G"))),
            Node("S", Node("P", None, Node("R")), Node("W")))

calls = {"open": 0, "most": 0}


def preorder(node, out):
    calls["open"] += 1
    calls["most"] = max(calls["most"], calls["open"])
    if node is not None:
        out.append(node.key)          # visit before both subtrees
        preorder(node.left, out)
        preorder(node.right, out)
    calls["open"] -= 1
    return out


def inorder(node, out):
    if node is not None:
        inorder(node.left, out)
        out.append(node.key)          # visit between the subtrees
        inorder(node.right, out)
    return out


def postorder(node, out):
    if node is not None:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.key)          # visit after both subtrees
    return out


def level_order(root):
    out, queue, widest = [], deque([root]), 1
    while queue:
        widest = max(widest, len(queue))
        node = queue.popleft()
        out.append(node.key)
        queue.extend(c for c in (node.left, node.right) if c is not None)
    return out, widest


print("preorder   ", " ".join(preorder(tree, [])))
print("inorder    ", " ".join(inorder(tree, [])))
print("postorder  ", " ".join(postorder(tree, [])))
order, widest = level_order(tree)
print("level order", " ".join(order))
print(f"most calls open at once: {calls['most']} (height 3, plus the root's call and one on an empty child)")
print(f"largest queue: {widest} nodes")

# An expression tree: (7 - 2) * (3 + 1). The three depth-first orders spell its three notations.
expr = Node("*", Node("-", Node("7"), Node("2")), Node("+", Node("3"), Node("1")))
print("prefix  (preorder): ", " ".join(preorder(expr, [])))
print("infix   (inorder):  ", " ".join(inorder(expr, [])), " <- the brackets are lost")
print("postfix (postorder):", " ".join(postorder(expr, [])))


def evaluate(node):
    """Postorder: both operands are ready before their operator."""
    if node.left is None:
        return int(node.key)
    a, b = evaluate(node.left), evaluate(node.right)
    return {"+": a + b, "-": a - b, "*": a * b}[node.key]


print("value:", evaluate(expr))

preorder    M E B H G S P R W
inorder     B E G H M P R S W
postorder   B G H E R P W S M
level order M E S B H P W G R
most calls open at once: 5 (height 3, plus the root's call and one on an empty child)
largest queue: 4 nodes
prefix  (preorder):  * - 7 2 + 3 1
infix   (inorder):   7 - 2 * 3 + 1  <- the brackets are lost
postfix (postorder): 7 2 - 3 1 + *
value: 20

Every node is entered once and every empty child is checked once, so each order runs in O(n) time. The memory is where they differ. A recursive walk keeps a call open for every node between the root and its current position, plus one for an empty child: at most 5 calls for this tree of height 3, O(h) in general, which is about log2 n for a balanced tree and n for a path. Level order keeps whole levels in its queue: 4 nodes at most here, and about half of all the nodes for a perfect tree, whose last level holds that many.

The expression tree shows why the choice matters. Preorder writes each operator before its operands (prefix notation) and postorder writes it after them, the postfix form that a stack evaluates. evaluate works in postorder for the same reason, since an operator needs both operands first, and returns 20. Inorder gives the familiar infix form, but without brackets it reads 7 − 2 × 3 + 1, which is a different expression, so a program that prints expressions in inorder has to put brackets around every subtree.

Telling the orders apart

Three clues identify most sequences. Preorder and level order always start with the root, and postorder always ends with it. Inorder lists a binary search tree’s keys in increasing order, as it does for this tree’s alphabetical keys. The leaves appear in the same left-to-right order in all three depth-first orders (B, G, R, W here), because each of them finishes a node’s left subtree before it starts the right one.

Other ways to walk the same orders

The recursive functions are short, and each alternative removes one of their weaknesses. An explicit stack takes over from the call stack, so a path of 100,000 nodes can no longer overflow it. Morris traversal produces inorder with O(1) extra memory by linking nodes to their in-order successors for a moment. Reading the queue’s length before each level turns level order into per-level answers, such as zig-zag order or the last node of each level.

Exercise: levels and zig-zag order

The exercise asks for the keys of each level, then for zig-zag order. Its tests include a path of 1,200 nodes, more than CPython’s 1,000 nested calls, so it needs the queue rather than recursion.

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


def levels(root):
    """The keys of each level, from the root down, each level left to right ([] for an empty tree)."""
    raise NotImplementedError("write levels")


def zigzag(root):
    """Like levels, but the 2nd, 4th, ... levels are read right to left."""
    raise NotImplementedError("write zigzag")

from tree_levels import Node, levels, zigzag


def lesson_tree():
    return Node("M", Node("E", Node("B"), Node("H", Node("G"))), Node("S", Node("P", None, Node("R")), Node("W")))


def perfect(height, start=1):
    """A perfect tree whose keys are numbered 1, 2, 3, ... in level order."""
    if height < 0:
        return None
    return Node(start, perfect(height - 1, 2 * start), perfect(height - 1, 2 * start + 1))


def test_empty_tree():
    """an empty tree has no levels"""
    assert levels(None) == []
    assert zigzag(None) == []


def test_single_node():
    """a single node is one level"""
    assert levels(Node(7)) == [[7]]
    assert zigzag(Node(7)) == [[7]]


def test_lesson_tree():
    """the lesson's tree, by levels and in zig-zag"""
    assert levels(lesson_tree()) == [["M"], ["E", "S"], ["B", "H", "P", "W"], ["G", "R"]]
    assert zigzag(lesson_tree()) == [["M"], ["S", "E"], ["B", "H", "P", "W"], ["R", "G"]]


def test_gaps_in_levels():
    """missing children leave gaps, and the levels close up around them"""
    t = Node(1, Node(2, None, Node(4, Node(6))), Node(3, None, Node(5, None, Node(7))))
    assert levels(t) == [[1], [2, 3], [4, 5], [6, 7]]
    assert zigzag(t) == [[1], [3, 2], [4, 5], [7, 6]]


def test_perfect_tree():
    """a perfect tree of height 10: level d holds the keys 2^d to 2^(d+1) - 1"""
    got = levels(perfect(10))
    assert got == [list(range(2 ** d, 2 ** (d + 1))) for d in range(11)]
    assert zigzag(perfect(10))[9] == list(range(2 ** 10 - 1, 2 ** 9 - 1, -1))


def test_long_path():
    """a path of 1,200 nodes, deeper than Python's default recursion limit, has 1,200 levels of one node"""
    root = node = Node(0)
    for k in range(1, 1_200):
        node.right = Node(k)
        node = node.right
    got = levels(root)
    assert len(got) == 1_200 and got[-1] == [1_199]
    assert zigzag(root)[777] == [777]

export class Node {
  constructor(key, left = null, right = null) {
    this.key = key;
    this.left = left;
    this.right = right;
  }
}

/** The keys of each level, from the root down, each level left to right ([] for an empty tree). */
export function levels(root) {
  throw new Error('write levels');
}

/** Like levels, but the 2nd, 4th, ... levels are read right to left. */
export function zigzag(root) {
  throw new Error('write zigzag');
}

import { test, assert } from 'mysmartcopilot:test';
import { Node, levels, zigzag } from './tree_levels.mjs';

const lessonTree = () =>
  new Node('M', new Node('E', new Node('B'), new Node('H', new Node('G'))), new Node('S', new Node('P', null, new Node('R')), new Node('W')));

function perfect(height, start = 1) {
  if (height < 0) return null;
  return new Node(start, perfect(height - 1, 2 * start), perfect(height - 1, 2 * start + 1));
}

const range = (from, to, step = 1) => {
  const out = [];
  for (let k = from; step > 0 ? k < to : k > to; k += step) out.push(k);
  return out;
};

test('an empty tree has no levels', () => {
  assert.deepEqual(levels(null), []);
  assert.deepEqual(zigzag(null), []);
});

test('a single node is one level', () => {
  assert.deepEqual(levels(new Node(7)), [[7]]);
  assert.deepEqual(zigzag(new Node(7)), [[7]]);
});

test("the lesson's tree, by levels and in zig-zag", () => {
  assert.deepEqual(levels(lessonTree()), [['M'], ['E', 'S'], ['B', 'H', 'P', 'W'], ['G', 'R']]);
  assert.deepEqual(zigzag(lessonTree()), [['M'], ['S', 'E'], ['B', 'H', 'P', 'W'], ['R', 'G']]);
});

test('missing children leave gaps, and the levels close up around them', () => {
  const t = new Node(1, new Node(2, null, new Node(4, new Node(6))), new Node(3, null, new Node(5, null, new Node(7))));
  assert.deepEqual(levels(t), [[1], [2, 3], [4, 5], [6, 7]]);
  assert.deepEqual(zigzag(t), [[1], [3, 2], [4, 5], [7, 6]]);
});

test('a perfect tree of height 10: level d holds the keys 2^d to 2^(d+1) - 1', () => {
  const got = levels(perfect(10));
  assert.deepEqual(got, range(0, 11).map((d) => range(2 ** d, 2 ** (d + 1))));
  assert.deepEqual(zigzag(perfect(10))[9], range(2 ** 10 - 1, 2 ** 9 - 1, -1));
});

test('a path of 1,200 nodes has 1,200 levels of one node', () => {
  const root = new Node(0);
  let node = root;
  for (let k = 1; k < 1200; k++) {
    node.right = new Node(k);
    node = node.right;
  }
  const got = levels(root);
  assert.equal(got.length, 1200);
  assert.deepEqual(got[got.length - 1], [1199]);
  assert.deepEqual(zigzag(root)[777], [777]);
});

All three depth-first orders with an explicit stack, and the depth limit reproduced Pro: opens with a Pro, Premium or Ultimate pass

Morris traversal: inorder in O(1) extra memory, with its proof Pro: opens with a Pro, Premium or Ultimate pass

Per-level answers, telling orders apart, and five languages Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Preorder, inorder and postorder differ only in when they visit the node; level order takes the tree one level at a time with a queue.
• All four take O(n) time. Recursion holds a call for every node on the current path; level order holds up to a whole level.
• Use postorder when a node needs its children’s results, inorder for a search tree’s sorted keys, preorder to write a tree out, and level order for the nodes nearest the root.
• Preorder and level order begin with the root, postorder ends with it, and the leaves keep their order in all three depth-first orders.