Lesson 16.1 · Binary Trees

Tree Vocabulary and TreeNode

Root, children, leaves, depth, height: the words every tree problem uses, and the TreeNode class behind them.

12 min

Think of it like this

A family tree drawn upside down: the oldest ancestor (root) at the top, each person with at most two children below. People with no children are leaves. Your depth is how many generations below the ancestor you are.

1.The words

Root: the top node. Children: a node's left and right nodes. Leaf: a node with no children. Depth of a node: edges from the root to it. Height of a tree: the depth of its deepest leaf (or the number of nodes on the longest root-to-leaf path, depending on convention: check the problem).

Trees are usually given in level order with nulls for missing children: [3, 9, 20, null, null, 15, 7] means 3 is the root, 9 and 20 are its children, 9 has no children, and 20 has children 15 and 7.

▶ Dry run: Reading a level-order arrayroot = [3, 9, 20, null, null, 15, 7]

Step 1/4Position 0 is the root: 3.

2.TreeNode and a first recursive function

Count nodes: an empty tree has 0; otherwise 1 plus the counts of both subtrees. Nearly every tree function has this shape: a base case for null, recursive calls on left and right, and a combine step.

Main.java

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

public class Main {
    static int count(TreeNode node) {
        if (node == null) return 0;
        return 1 + count(node.left) + count(node.right);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        System.out.println(count(root));
    }
}

Output

Remember

Every node is the root of a subtree.
Level-order arrays with nulls describe trees in problems.
Base case null, recurse left and right, combine.

Common mistakes

Mixing up depth (from the root down) and height (from the node down to leaves).
Forgetting the null base case.

Words used in this lesson

Binary tree: A tree where each node has at most two children.
Leaf: A node with no children.
Subtree: A node together with everything below it.
Level order: Listing nodes level by level, left to right.

Command Palette

Tree Vocabulary and TreeNode

1.The words

2.TreeNode and a first recursive function