Trees: Data With Branches

Not everything is a line

Arrays and linked lists are lines: one item after another. But lots of data branches: folders inside folders, a company's boss and teams, a family tree. That shape is a tree.

In a binary tree each node has at most two children: left and right. It's just a linked list node with two arrows instead of one:

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class Main {
    public static void main(String[] args) {
        //        8
        //       / \
        //      3   10
        //     / \    \
        //    1   6    14
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);

        System.out.println("root: " + root.value);
        System.out.println("root's children: " + root.left.value + " and " + root.right.value);
        System.out.println("is 6 a leaf? " + (root.left.right.left == null && root.left.right.right == null));
    }
}

Output

root: 8
root's children: 3 and 10
is 6 a leaf? true

Trees love recursion

A tree is made of smaller trees: the left child is the root of its own little tree, and so is the right. So most tree questions are answered with the same recipe:

• Base case: an empty tree (null) – the answer is usually 0.
• Recursive step: ask the left subtree, ask the right subtree, combine with this node.

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class Main {
    static int count(TreeNode node) {
        if (node == null) return 0;
        return 1 + count(node.left) + count(node.right);
    }

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);
        root.left.right.left = new TreeNode(4);
        System.out.println("nodes: " + count(root));
        System.out.println("height: " + height(root));
    }
}

Output

nodes: 7
height: 4

Remember: Trust the recursion: assume count(node.left) already gives the right answer for the left side.