Lesson 14 of 2419 min read

Trees and Traversals

Hierarchies instead of sequences. Four ways to walk a tree, and once you can walk one, a large fraction of interview questions become short.

By the end: Traverse a tree four ways, recursively and iteratively.

A tree is a hierarchy: one root, and every node has children. No cycles, and exactly one path from the root to any node.

A binary tree limits each node to at most two children, left and right. That is what almost every interview question uses, and the reason trees are so heavily tested is that they reward clear recursive thinking and nothing else.

A node, and a tree built from nodes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

//         1
//        / \
//       2   3
//      / \
//     4   5
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);

console.log('root:', root.val);
console.log('root.left:', root.left.val, '| root.right:', root.right.val);
console.log('leftmost leaf:', root.left.left.val);
console.log('a leaf has no children:', root.left.left.left, root.left.left.right);

Output

Vocabulary you will be expected to use

Root — the top node. Leaf — a node with no children.
Depth of a node — how many edges from the root. The root has depth 0.
Height of a tree — the longest path from root to leaf, counted in edges or nodes depending on who is asking. Say which you mean.
Balanced — the left and right subtree heights differ by at most one, everywhere. A balanced tree of n nodes has height O(log n).
Complete — every level full except possibly the last, which fills left to right. This is what a heap is, and it is why a heap can live in an array.
Subtree — any node together with all of its descendants. Every recursive call in this lesson operates on a subtree.

Helpers for this lesson

Building trees from arrays, so examples stay readable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class TreeNode {
  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
}

/* Level-order array, with null for a missing node. This is how LeetCode
   presents trees, so it is worth being able to build one. */
function buildTree(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let head = 0, i = 1;

  while (head < queue.length && i < values.length) {
    const node = queue[head++];
    if (i < values.length) {
      const v = values[i++];
      if (v !== null) { node.left = new TreeNode(v); queue.push(node.left); }
    }
    if (i < values.length) {
      const v = values[i++];
      if (v !== null) { node.right = new TreeNode(v); queue.push(node.right); }
    }
  }
  return root;
}

const t = buildTree([1, 2, 3, 4, 5, null, 6]);
console.log('root', t.val, '| left', t.left.val, '| right', t.right.val);
console.log('2 has children', t.left.left.val, 'and', t.left.right.val);
console.log('3 has no left child:', t.right.left, '| right child:', t.right.right.val);

Output

The four traversals

There are exactly four ways to walk a binary tree, and the difference between the first three is only when you record the current node relative to recursing.

Preorder, inorder, postorder: one line moves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const t = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));

// PREorder: me, then left, then right. Top-down.
function preorder(node, out = []) {
  if (!node) return out;
  out.push(node.val);
  preorder(node.left, out);
  preorder(node.right, out);
  return out;
}

// INorder: left, then me, then right. On a BST this gives sorted order.
function inorder(node, out = []) {
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.val);
  inorder(node.right, out);
  return out;
}

// POSTorder: left, then right, then me. Bottom-up: children before parents.
function postorder(node, out = []) {
  if (!node) return out;
  postorder(node.left, out);
  postorder(node.right, out);
  out.push(node.val);
  return out;
}

console.log('preorder: ', preorder(t));    // [1,2,4,5,3]
console.log('inorder:  ', inorder(t));     // [4,2,5,1,3]
console.log('postorder:', postorder(t));   // [4,5,2,3,1]

Output

Level order: the fourth traversal, and the only iterative one by nature

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const t = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));

function levelOrder(root) {
  if (!root) return [];
  const out = [];
  let queue = [root], head = 0;              // head pointer, never shift

  while (head < queue.length) {
    const levelSize = queue.length - head;   // freeze the count for this level
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    out.push(level);
  }
  return out;
}

console.log('levels:', levelOrder(t));
console.log('depth:', levelOrder(t).length);
console.log('rightmost of each level:', levelOrder(t).map(l => l[l.length - 1]));
console.log('empty:', levelOrder(null));

Output

Iterative traversals

Interviewers ask for these to check you understand that recursion is a stack. Preorder is easy; inorder is the one worth practising.

Preorder and inorder without recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const t = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));

function preorderIterative(root) {
  const out = [], stack = [];
  if (root) stack.push(root);
  while (stack.length) {
    const node = stack.pop();
    out.push(node.val);
    if (node.right) stack.push(node.right);   // right first so left comes off first
    if (node.left) stack.push(node.left);
  }
  return out;
}

function inorderIterative(root) {
  const out = [], stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }   // run all the way left
    node = stack.pop();                                     // visit
    out.push(node.val);
    node = node.right;                                      // then go right once
  }
  return out;
}

// Postorder trick: do preorder with the children reversed, then reverse the result.
function postorderIterative(root) {
  const out = [], stack = [];
  if (root) stack.push(root);
  while (stack.length) {
    const node = stack.pop();
    out.push(node.val);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return out.reverse();
}

console.log('preorder  iterative:', preorderIterative(t));
console.log('inorder   iterative:', inorderIterative(t));
console.log('postorder iterative:', postorderIterative(t));

Output

The bottom-up pattern

Most tree questions are one recursive function that returns something useful from each subtree. Write the return value down before you write the code and the rest is mechanical.

Height, count, balance, diameter: all one shape

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const t = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));

// Return: the height of this subtree.
const height = (n) => n === null ? 0 : 1 + Math.max(height(n.left), height(n.right));

// Return: how many nodes are in this subtree.
const count = (n) => n === null ? 0 : 1 + count(n.left) + count(n.right);

// Return: the sum of this subtree.
const sum = (n) => n === null ? 0 : n.val + sum(n.left) + sum(n.right);

// Return: -1 if unbalanced anywhere below, otherwise the height. One pass.
function balancedHeight(n) {
  if (n === null) return 0;
  const l = balancedHeight(n.left);
  if (l === -1) return -1;                 // give up early
  const r = balancedHeight(n.right);
  if (r === -1) return -1;
  if (Math.abs(l - r) > 1) return -1;
  return 1 + Math.max(l, r);
}
const isBalanced = (n) => balancedHeight(n) !== -1;

// Diameter: the longest path anywhere. Return the height, but record the best
// path THROUGH each node as a side effect. This two-things-at-once trick is
// extremely common.
function diameter(root) {
  let best = 0;
  function h(n) {
    if (n === null) return 0;
    const l = h(n.left), r = h(n.right);
    best = Math.max(best, l + r);        // path down the left and up the right
    return 1 + Math.max(l, r);
  }
  h(root);
  return best;
}

console.log('height:', height(t), '| nodes:', count(t), '| sum:', sum(t));
console.log('balanced:', isBalanced(t));
console.log('diameter (edges):', diameter(t));

const lopsided = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4))));
console.log('lopsided balanced?', isBalanced(lopsided), '| height:', height(lopsided));

Output

Passing information downwards

Depth, paths, and range checks come down from the parent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const t = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));

// Every root-to-leaf path. The path so far is passed down; copy on push, pop on return.
function allPaths(node, path = [], out = []) {
  if (node === null) return out;
  path.push(node.val);
  if (node.left === null && node.right === null) {
    out.push([...path]);                    // copy, or every result aliases the same array
  } else {
    allPaths(node.left, path, out);
    allPaths(node.right, path, out);
  }
  path.pop();                                // undo before returning to the parent
  return out;
}

// Does any root-to-leaf path sum to the target?
function hasPathSum(node, target) {
  if (node === null) return false;
  const remaining = target - node.val;
  if (node.left === null && node.right === null) return remaining === 0;
  return hasPathSum(node.left, remaining) || hasPathSum(node.right, remaining);
}

console.log('all paths:', allPaths(t));
console.log('path summing to 7 (1→2→4):', hasPathSum(t, 7));
console.log('path summing to 4:', hasPathSum(t, 4), '(1→3 is 4)');
console.log('path summing to 99:', hasPathSum(t, 99));

Output

Comparing and transforming trees

Same tree, symmetric tree, invert, lowest common ancestor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }

// Two trees identical? Compare structure and values together.
function isSame(a, b) {
  if (a === null && b === null) return true;
  if (a === null || b === null) return false;      // one ran out
  return a.val === b.val && isSame(a.left, b.left) && isSame(a.right, b.right);
}

// Symmetric: is the tree a mirror of itself? Compare outer with outer, inner with inner.
function isSymmetric(root) {
  const mirror = (a, b) => {
    if (a === null && b === null) return true;
    if (a === null || b === null) return false;
    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
  };
  return root === null ? true : mirror(root.left, root.right);
}

// Invert: swap children everywhere.
function invert(node) {
  if (node === null) return null;
  [node.left, node.right] = [invert(node.right), invert(node.left)];
  return node;
}

// Lowest common ancestor in a plain binary tree.
function lca(node, p, q) {
  if (node === null || node.val === p || node.val === q) return node;
  const left = lca(node.left, p, q);
  const right = lca(node.right, p, q);
  if (left && right) return node;      // p and q are on opposite sides: this is it
  return left ?? right;                 // both on one side: pass it up
}

const a = new TreeNode(1, new TreeNode(2), new TreeNode(3));
const b = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log('isSame:', isSame(a, b), '| different:', isSame(a, new TreeNode(1, new TreeNode(3))));

const sym = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)),
                            new TreeNode(2, new TreeNode(4), new TreeNode(3)));
console.log('isSymmetric:', isSymmetric(sym), '| not:', isSymmetric(a));

const inv = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7));
const toArr = (n, o = []) => { if (n) { toArr(n.left, o); o.push(n.val); toArr(n.right, o); } return o; };
console.log('before invert:', toArr(inv));
console.log('after invert: ', toArr(invert(inv)));

const big = new TreeNode(3, new TreeNode(5, new TreeNode(6), new TreeNode(2)), new TreeNode(1));
console.log('LCA of 6 and 2:', lca(big, 6, 2).val, '| LCA of 6 and 1:', lca(big, 6, 1).val);

Output

Serialising a tree

"Turn a tree into a string and back" is a favourite because it tests whether you understand that a single traversal is not enough to reconstruct a tree — unless you record the nulls.

Serialise and deserialise with explicit nulls

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }

function serialize(root) {
  const parts = [];
  (function walk(node) {
    if (node === null) { parts.push('#'); return; }   // record the gap
    parts.push(String(node.val));
    walk(node.left);
    walk(node.right);
  })(root);
  return parts.join(',');
}

function deserialize(data) {
  const parts = data.split(',');
  let i = 0;
  function build() {
    const token = parts[i++];
    if (token === '#') return null;
    return new TreeNode(Number(token), build(), build());   // order matters
  }
  return build();
}

const t = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
const s = serialize(t);
console.log('serialised:', s);
const rebuilt = deserialize(s);
console.log('round trip matches:', serialize(rebuilt) === s);
console.log('empty tree:', serialize(null), '→ round trip:', serialize(deserialize(serialize(null))));

Output

Your turn: five tree problems

maxDepth(root) — the warm-up, in one line.
rightSideView(root) — the rightmost value at each level, top to bottom. Level order and take the last of each level.
goodNodes(root) — count nodes whose value is at least as large as every value on the path from the root. Pass the running maximum down.
zigzagLevelOrder(root) — level order, but alternate directions each level.
buildFromPreorderInorder(pre, ino) — reconstruct the tree. The first preorder value is the root; find it in the inorder array to learn how many nodes are in the left subtree.

Editable. Fill them in, then run.

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
function buildTree(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const q = [root]; let h = 0, i = 1;
  while (h < q.length && i < values.length) {
    const n = q[h++];
    if (i < values.length) { const v = values[i++]; if (v !== null) { n.left = new TreeNode(v); q.push(n.left); } }
    if (i < values.length) { const v = values[i++]; if (v !== null) { n.right = new TreeNode(v); q.push(n.right); } }
  }
  return root;
}
const inorderOf = (n, o = []) => { if (n) { inorderOf(n.left, o); o.push(n.val); inorderOf(n.right, o); } return o; };

function maxDepth(root) {
  // one line
}

function rightSideView(root) {
  // level order, last of each level
}

function goodNodes(root) {
  // pass the max seen so far down
}

function zigzagLevelOrder(root) {
  // level order, reverse alternate levels
}

function buildFromPreorderInorder(pre, ino) {
  // root is pre[0]; split ino at its position
}

console.log(maxDepth(buildTree([3, 9, 20, null, null, 15, 7])));        // 3
console.log(rightSideView(buildTree([1, 2, 3, null, 5, null, 4])));     // [1,3,4]
console.log(goodNodes(buildTree([3, 1, 4, 3, null, 1, 5])));            // 4
console.log(zigzagLevelOrder(buildTree([3, 9, 20, null, null, 15, 7])));// [[3],[20,9],[15,7]]
console.log(inorderOf(buildFromPreorderInorder([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])));  // [9,3,15,20,7]

Output

Recap

Tree operations cost O(height): O(log n) balanced, O(n) degenerate. Answer in terms of height.
Preorder, inorder and postorder differ only in when you record the node; level order needs a queue.
Preorder for information coming down, postorder for answers coming up, inorder for sorted order on a BST.
Most tree problems are one recursive function; decide what it returns before writing it, and use the return-one-thing-record-another trick for path problems.
When building paths, copy with [...path] and always pop before returning to the parent.

Vocabulary you will be expected to use

Helpers for this lesson

The four traversals

Iterative traversals

The bottom-up pattern

Passing information downwards

Comparing and transforming trees

Serialising a tree

Your turn: five tree problems

Recap

New writing, when it lands.