Trees

Branching instead of chaining

A linked list node points at one other node. A tree node points at several. That single change gives you a structure for anything hierarchical.

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

This is a binary tree — at most two children per node. Trees can have any number; two is the most common and the easiest to reason about.

Some vocabulary, all of which appears in real code:

Things that are naturally trees

• A file system — folders containing folders containing files
• An organisation chart
• The HTML structure of a web page
• A robot’s subsystem hierarchy, where a drivetrain contains modules which contain motors
• Any decision process where each answer leads to further questions

If a problem has parents and children, or containment, it is probably a tree.

Walking a tree

Because each subtree is itself a tree, recursion fits naturally. The method calls itself on each child and the structure handles the rest.

static void printAll(TreeNode node) {
    if (node == null) return;        // base case: nothing here

    printAll(node.left);             // everything on the left
    System.out.println(node.value);  // this node
    printAll(node.right);            // everything on the right
}

The if (node == null) return; is what stops the recursion. Every tree method needs it, and forgetting it gives a NullPointerException at the first leaf.

Moving the println changes the order you visit things:

Traversal orders

Level-order is the odd one out — it needs a queue rather than recursion:

static void printByLevel(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.value);
        if (node.left != null)  queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Recursive measurements

Most tree questions have the same shape: combine the answers from the children.

static int countNodes(TreeNode node) {
    if (node == null) return 0;
    return 1 + countNodes(node.left) + countNodes(node.right);
}

static int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

static int sum(TreeNode node) {
    if (node == null) return 0;
    return node.value + sum(node.left) + sum(node.right);
}

All three follow one template: return a base value for null, otherwise combine this node with the results from both children. Once you see the pattern, most tree problems become a matter of choosing how to combine.

Binary search trees

A binary tree becomes genuinely useful when you impose a rule: everything in the left subtree is smaller than the node, and everything in the right subtree is larger.

static TreeNode insert(TreeNode node, int value) {
    if (node == null) return new TreeNode(value);

    if (value < node.value) {
        node.left = insert(node.left, value);
    } else if (value > node.value) {
        node.right = insert(node.right, value);
    }
    return node;                     // equal values ignored
}

static boolean contains(TreeNode node, int value) {
    if (node == null) return false;
    if (value == node.value) return true;
    return value < node.value
        ? contains(node.left, value)
        : contains(node.right, value);
}

Each comparison discards half the remaining tree, so searching a balanced tree with a million nodes takes about 20 comparisons rather than a million.

// inserting 1, 2, 3, 4, 5 in order gives:
// 1 -> 2 -> 3 -> 4 -> 5

Use the library

You will rarely write a search tree in production. Java provides balanced ones:

import java.util.TreeMap;
import java.util.TreeSet;

TreeSet<Integer> values = new TreeSet<>();
values.add(50);
values.add(10);
values.add(30);

System.out.println(values);              // [10, 30, 50] — always sorted
System.out.println(values.first());      // 10
System.out.println(values.last());       // 50
System.out.println(values.ceiling(20));  // 30 — smallest value >= 20
System.out.println(values.floor(20));    // 10 — largest value <= 20

ceiling and floor are the reason to choose TreeSet over HashSet. A hash set answers “is this present”; a tree set also answers “what is the nearest value to this”, which a hash set cannot do at any speed.

TreeMap does the same for key-value pairs, keeping keys sorted.

Next

Related