Binary tree representation

The standard linked representation is one object per node, holding a value and a reference to each child. The root reference is the tree. All the traversal and query code in this chapter takes a TreeNode as its argument and works recursively on its children.

A tree needs no wrapper class for most problems; contest-style code passes the root around. A production class would hold the root plus a size counter and guard invariants.

1static class TreeNode {
2    int val;
3    TreeNode left, right;                        // null means "no child on that side"
4    TreeNode(int val) { this.val = val; }
5    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
6}

The side of a child is part of the tree's identity. Building the tree 1 with children 2 and 3, where 2 has the child 4, takes explicit assignments to left and right. A node with only a right child is not the same tree as a node with only a left child, even though both have one child.

The constructor with two children makes small trees readable as nested expressions: new TreeNode(1, new TreeNode(2, new TreeNode(4), null), new TreeNode(3)).

1static TreeNode sample() {
2    TreeNode root = new TreeNode(1);
3    root.left = new TreeNode(2);
4    root.right = new TreeNode(3);
5    root.left.left = new TreeNode(4);            // 4 is the LEFT child of 2; 2 has no right child
6    return root;
7}

Trees are described in tests as **level-order lists** with # (or null) for a missing child, such as “3 9 20 # # 15 7”: the root is 3, its children are 9 and 20, 9 has no children (two #), and 20 has children 15 and 7. Building the tree takes a queue: each node taken from the front receives the next two tokens as its left and right children.

Every animation in this chapter accepts exactly this text format, so you can type your own trees. A token # is consumed by a missing child but creates no node and adds nothing to the queue.

1static TreeNode fromLevelOrder(String[] tokens) {
2    if (tokens.length == 0 || tokens[0].equals("#")) return null;
3    TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
4    Deque<TreeNode> queue = new ArrayDeque<>(List.of(root));
5    int i = 1;
6    while (!queue.isEmpty() && i < tokens.length) {
7        TreeNode n = queue.poll();
8        if (i < tokens.length && !tokens[i++].equals("#")) { n.left = new TreeNode(Integer.parseInt(tokens[i - 1])); queue.add(n.left); }
9        if (i < tokens.length && !tokens[i++].equals("#")) { n.right = new TreeNode(Integer.parseInt(tokens[i - 1])); queue.add(n.right); }
10    }
11    return root;
12}
13
14// the same idea recursively: a perfect tree of the given height, numbered by preorder
15static TreeNode perfect(int height, int[] next) {
16    if (height < 0) return null;
17    TreeNode n = new TreeNode(next[0]++);
18    n.left = perfect(height - 1, next);
19    n.right = perfect(height - 1, next);
20    return n;
21}

1static void preorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;                       // empty subtree: nothing to visit
3    out.add(n.val);                              // visit the node first
4    preorder(n.left, out);
5    preorder(n.right, out);
6}
7static void inorder(TreeNode n, List<Integer> out) {
8    if (n == null) return;
9    inorder(n.left, out);
10    out.add(n.val);                              // visit between the two subtrees
11    inorder(n.right, out);
12}
13static void postorder(TreeNode n, List<Integer> out) {
14    if (n == null) return;
15    postorder(n.left, out);
16    postorder(n.right, out);
17    out.add(n.val);                              // visit after both subtrees
18}
19static List<Integer> levelOrder(TreeNode root) {
20    List<Integer> out = new ArrayList<>();
21    Deque<TreeNode> queue = new ArrayDeque<>();
22    if (root != null) queue.add(root);
23    while (!queue.isEmpty()) {
24        TreeNode n = queue.poll();               // oldest node first
25        out.add(n.val);
26        if (n.left != null) queue.add(n.left);
27        if (n.right != null) queue.add(n.right);
28    }
29    return out;
30}

A **complete** binary tree fits in an array with no pointers. Store the root at index 0 and, level by level, left to right, everything else; then the children of index i are at 2i + 1 and 2i + 2, and the parent is at (i - 1) / 2 (integer division). Heaps use exactly this layout, and it is cache-friendly and compact.

For an incomplete tree the array has holes (nulls), and the waste can be huge: a chain of n left children needs 2^n - 1 slots, so a chain of 5 nodes uses a 31-slot array and a chain of 20 needs over a million. Linked nodes cost memory in proportion to n, so use the array form only when the tree is known to be nearly complete.

1static Integer[] toHeapArray(TreeNode root) {
2    int h = height(root);
3    Integer[] a = new Integer[(1 << (h + 1)) - 1];   // room for a perfect tree of this height
4    fill(root, 0, a);
5    return a;
6}
7static void fill(TreeNode n, int i, Integer[] a) {
8    if (n == null) return;
9    a[i] = n.val;
10    fill(n.left, 2 * i + 1, a);
11    fill(n.right, 2 * i + 2, a);
12}
13static int height(TreeNode n) { return n == null ? -1 : 1 + Math.max(height(n.left), height(n.right)); }

Every leaf has two null child references, and a node with one child has one. Counting them shows a fixed relation: a binary tree with n nodes has **n + 1** null references. All the base cases of tree recursion are the same null check: if (n == null) return ...;.

The cost of forgetting it is a NullPointerException at the first leaf. Choose the base value carefully, because it flows into every parent: 0 for counts and sums, -1 for height, true for 'all nodes satisfy', false for 'any node satisfies', null for 'find a node'.

1static int nullLinks(TreeNode n) {
2    if (n == null) return 1;                     // this empty link is one of the n + 1
3    return nullLinks(n.left) + nullLinks(n.right);
4}