Algorithms and Data Structures · Chapter 7

Trees and heaps

Lists, stacks and queues arrange data in a row. A tree branches: every node can have several successors. In a well-built search tree you find a value in just a few steps, and a heap hands you the smallest element right away. Almost every method on trees is recursive, because every part of a tree is itself a tree.

Terms

In a binary tree, every node has at most two children, a left one and a right one. In the tasks, a node looks like this:

1class TreeNode {2    int value;3    TreeNode left;4    TreeNode right;5}

The root is the top node, the only one without a parent. Through it you reach the whole tree.
A leaf has no children: left and right are null. All other nodes are called inner nodes.
A subtree is a node with everything hanging below it. So the left subtree of the root is a tree in its own right.
Here, the height counts the levels: a single node has height 1, an empty tree height 0. Some books count the edges instead, then everything is 1 smaller.

Recursion and traversal

A method on a tree almost always follows the same pattern: the base case is the empty tree (node == null), otherwise you process the node and call yourself for node.left and node.right. Every node is visited exactly once, which costs O(n).

Visiting all nodes is called traversing the tree. The three usual orders differ only in when the node itself is handled:

Preorder: node, left, right. The root comes first.
Inorder: left, node, right. The root is in the middle.
Postorder: left, right, node. The root comes last.

1public class Main {2    static int countNodes(TreeNode node) {3        if (node == null) {4            return 0;5        }6        return 1 + countNodes(node.left) + countNodes(node.right);7    }8
9    static int height(TreeNode node) {10        if (node == null) {11            return 0;12        }13        return 1 + Math.max(height(node.left), height(node.right));14    }15
16    static void preorder(TreeNode node) {17        if (node == null) {18            return;19        }20        System.out.print(node.value + " ");21        preorder(node.left);22        preorder(node.right);23    }24
25    static void inorder(TreeNode node) {26        if (node == null) {27            return;28        }29        inorder(node.left);30        System.out.print(node.value + " ");31        inorder(node.right);32    }33
34    static void postorder(TreeNode node) {35        if (node == null) {36            return;37        }38        postorder(node.left);39        postorder(node.right);40        System.out.print(node.value + " ");41    }42
43    public static void main(String[] args) {44        //        145        //       / \46        //      2   347        //     / \48        //    4   549        TreeNode root = new TreeNode(1,50                new TreeNode(2, new TreeNode(4), new TreeNode(5)),51                new TreeNode(3));52        System.out.println("Nodes: " + countNodes(root));53        System.out.println("Height: " + height(root));54        System.out.print("Preorder:  ");55        preorder(root);56        System.out.println();57        System.out.print("Inorder:   ");58        inorder(root);59        System.out.println();60        System.out.print("Postorder: ");61        postorder(root);62        System.out.println();63    }64}65
66class TreeNode {67    int value;68    TreeNode left;69    TreeNode right;70
71    TreeNode(int value) {72        this.value = value;73    }74
75    TreeNode(int value, TreeNode left, TreeNode right) {76        this.value = value;77        this.left = left;78        this.right = right;79    }80}

For the tree in the example, this gives 1 2 4 5 3, 4 2 5 1 3 and 4 5 2 3 1. In an exam it helps to draw the tree and tick off every node when you visit it.

Binary search trees

A binary search tree keeps the values in order: for every node, all values in the left subtree are smaller, all values in the right subtree are larger. When searching, you compare with the node and go left or right, just like binary search in an array. A new value is inserted where the search hits null.

The smallest value is at the very bottom left, the largest at the very bottom right.
Inorder gives the values sorted.
Searching and inserting take as many steps as the tree is high. If it is balanced, that is about log₂ n, so O(log n): 1,000,000 values in around 20 levels.
If you insert values that are already sorted (1, 2, 3, …), every new node hangs to the right of the previous one. The tree degenerates into a list, and searching then costs O(n). Self-balancing trees (AVL, red-black, in Java TreeMap) prevent this.

1public class Main {2    static TreeNode insert(TreeNode root, int value) {3        if (root == null) {4            return new TreeNode(value);5        }6        if (value < root.value) {7            root.left = insert(root.left, value);8        } else if (value > root.value) {9            root.right = insert(root.right, value);10        }11        return root;12    }13
14    static boolean contains(TreeNode root, int value) {15        TreeNode node = root;16        while (node != null) {17            if (value == node.value) {18                return true;19            }20            node = value < node.value ? node.left : node.right;21        }22        return false;23    }24
25    static int min(TreeNode root) {26        TreeNode node = root;27        while (node.left != null) {28            node = node.left;29        }30        return node.value;31    }32
33    static void inorder(TreeNode node) {34        if (node == null) {35            return;36        }37        inorder(node.left);38        System.out.print(node.value + " ");39        inorder(node.right);40    }41
42    public static void main(String[] args) {43        TreeNode root = null;44        for (int v : new int[] {50, 30, 70, 20, 40, 60, 80}) {45            root = insert(root, v);46        }47        System.out.println("contains 40? " + contains(root, 40));48        System.out.println("contains 45? " + contains(root, 45));49        System.out.println("min: " + min(root));50        System.out.print("sorted: ");51        inorder(root);52        System.out.println();53    }54}55
56class TreeNode {57    int value;58    TreeNode left;59    TreeNode right;60
61    TreeNode(int value) {62        this.value = value;63    }64}

Heaps in an array

A min-heap is a binary tree with the heap property: every node is smaller than or equal to its children. So the minimum is always at the root. Unlike in a search tree, siblings are not ordered among each other.

A heap is always complete, filled level by level from the left. That is why it fits into an array without gaps:

root at index 0
children of i: 2 * i + 1 and 2 * i + 2
parent of i: (i - 1) / 2 (integer division)

Insert: append at the end and let it sift up as long as the value is smaller than its parent. Remove the minimum: put the last element at index 0 and let it sift down, always swapping with the smaller child. Both run at most once from top to bottom through the tree: O(log n). Java offers this ready-made as PriorityQueue.

1import java.util.Arrays;2
3public class Main {4    static int[] data = new int[10];5    static int size = 0;6
7    static void insert(int value) {8        data[size] = value;9        int i = size;10        size++;11        // sift up: swap with the parent while smaller12        while (i > 0 && data[i] < data[(i - 1) / 2]) {13            swap(i, (i - 1) / 2);14            i = (i - 1) / 2;15        }16    }17
18    static int poll() {19        int min = data[0];20        size--;21        data[0] = data[size];22        int i = 0;23        // sift down: swap with the smaller child while larger24        while (2 * i + 1 < size) {25            int child = 2 * i + 1;26            if (child + 1 < size && data[child + 1] < data[child]) {27                child++;28            }29            if (data[i] <= data[child]) {30                break;31            }32            swap(i, child);33            i = child;34        }35        return min;36    }37
38    static void swap(int i, int j) {39        int tmp = data[i];40        data[i] = data[j];41        data[j] = tmp;42    }43
44    public static void main(String[] args) {45        for (int v : new int[] {5, 3, 8, 1, 4}) {46            insert(v);47            System.out.println("insert " + v + ": " + Arrays.toString(Arrays.copyOf(data, size)));48        }49        System.out.println("poll: " + poll());50        System.out.println("heap: " + Arrays.toString(Arrays.copyOf(data, size)));51    }52}

Heapsort

Heapsort sorts with a max-heap directly in the array:

Build the heap: from a.length / 2 - 1 down to 0, let every inner node sift down. After that, the maximum is at index 0.
Swap the maximum with the last element of the heap. It is now at its final place, and the heap is one element shorter. Let the new root sift down and repeat.

Each sift-down costs O(log n), and it happens n times: O(n log n), even in the worst case. Unlike quicksort, heapsort needs no extra memory and has no bad case with O(n²). On the other hand it is not stable: equal values can swap their order.

1import java.util.Arrays;2
3public class Main {4    static void heapSort(int[] a) {5        // 1. build a max-heap: let every inner node sink, from back to front6        for (int i = a.length / 2 - 1; i >= 0; i--) {7            siftDown(a, i, a.length);8        }9        // 2. move the maximum to the end, shrink the heap, repair it10        for (int end = a.length - 1; end > 0; end--) {11            swap(a, 0, end);12            siftDown(a, 0, end);13        }14    }15
16    static void siftDown(int[] a, int i, int size) {17        while (2 * i + 1 < size) {18            int child = 2 * i + 1;19            if (child + 1 < size && a[child + 1] > a[child]) {20                child++;21            }22            if (a[i] >= a[child]) {23                return;24            }25            swap(a, i, child);26            i = child;27        }28    }29
30    static void swap(int[] a, int i, int j) {31        int tmp = a[i];32        a[i] = a[j];33        a[j] = tmp;34    }35
36    public static void main(String[] args) {37        int[] a = {4, 10, 3, 5, 1};38        heapSort(a);39        System.out.println(Arrays.toString(a));40    }41}

Common mistakes

Recursive call not hooked in
insert(root.left, value); on its own does create a new node, but nobody keeps it. Correct is root.left = insert(root.left, value);. The same goes for the first insert into an empty tree: root = insert(root, 5);, otherwise root stays null.
Search tree checked only against the children
It is not enough that every left child is smaller and every right child is larger. In the tree with root 8, left child 3 and its right child 9, every pair fits, yet the 9 is in the left subtree of the 8. Check every node against a lower and an upper bound that you pass down on the way.
Wrong indices in the heap
With the root at index 0, the children are 2 * i + 1 and 2 * i + 2. The formulas 2 * i and 2 * i + 1 only apply if the root is at index 1. And when sifting down, a child only exists if its index is smaller than size, not smaller than data.length: beyond that there are old values.