☕ DSA Java Articles

Topics › Binary Trees › Traversals

Introduction to Trees

Easy TUF ID 2865 A2Z

Java source ↗ Edit this article ↗

What this covers

Arrays, linked lists, stacks and queues are linear: every element has at most one successor, so the data forms a line. A tree is the simplest hierarchical structure: one element sits at the top, and every element can have several elements directly below it. File systems, organisation charts, the HTML document of a web page, the call tree of a recursive function and the decisions of a game all have this shape.

This article fixes the vocabulary used throughout the tree section, introduces the binary-tree node in Java, shows how to measure a tree (size, height, depth, leaves), defines the named kinds of binary tree (full, complete, perfect, balanced, degenerate) with a checker for each, and ends with the counting facts that explain why balanced trees are fast. Every function below is in the Java file, tested in main.

Vocabulary

We will use this tree throughout:

            1            depth 0
          /   \
         2     3         depth 1
        / \     \
       4   5     6       depth 2
          /
         7               depth 3

A binary tree is a tree in which every node has at most two children, and they are distinguished as the left child and the right child. A node with only a left child is a different tree from a node with only a right child.

The binary-tree node

A node stores its value and two references, either of which may be null. The tree as a whole is identified by a reference to its root, and the empty tree is simply null.

static 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; }
}

The three-argument constructor lets us write the example tree as one nested expression whose shape follows the picture:

static TreeNode exampleTree() {
    return new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7), null)),
            new TreeNode(3, null, new TreeNode(6)));
}

Measuring a tree

Almost every measurement follows the same recursive recipe: handle the empty tree, then combine the answers of the two subtrees with the root. The size is one for the root plus the sizes of both subtrees.

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

Every node except the root has exactly one edge leading up to its parent, so a non-empty tree with n nodes has exactly n - 1 edges. Counting edges directly confirms this:

static int countEdges(TreeNode root) {
    if (root == null) return 0;
    int here = (root.left != null ? 1 : 0) + (root.right != null ? 1 : 0);
    return here + countEdges(root.left) + countEdges(root.right);
}

The height (in levels) is one for the root plus the taller of the two subtree heights. For the example tree that is 1 + max(3, 2) = 4.

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

Depth is the opposite direction: it is measured from the root down to one particular node. The search below returns -1 when the value is absent, and adds one for every level it climbs back up.

static int depthOf(TreeNode root, int target) {
    if (root == null) return -1;
    if (root.val == target) return 0;
    int d = depthOf(root.left, target);
    if (d == -1) d = depthOf(root.right, target);
    return d == -1 ? -1 : d + 1;
}

A leaf is recognised by having no children, so counting leaves stops the recursion one level earlier than counting nodes.

static int countLeaves(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    return countLeaves(root.left) + countLeaves(root.right);
}

All of these visit each node once, so they run in O(n) time and use O(h) stack space for the recursion, where h is the height.

Kinds of binary trees

These names appear constantly in problem statements and in the analysis of algorithms, so it pays to know them precisely.

Full (also called proper or strict): every node has either zero or two children, never exactly one. In a full binary tree the number of leaves is always the number of internal nodes plus one, which the tests check.

static boolean isFull(TreeNode root) {
    if (root == null) return true;
    if ((root.left == null) != (root.right == null)) return false;    // exactly one child
    return isFull(root.left) && isFull(root.right);
}

The condition (root.left == null) != (root.right == null) is true exactly when one child is present and the other is not.

Complete: every level is completely filled except possibly the last, and the last level is filled from the left with no gaps. Heaps are stored as complete trees, which is why they fit in an array. The cleanest test reads the tree level by level including the null positions: once a missing position has been seen, no real node may follow.

static boolean isComplete(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();       // LinkedList, because ArrayDeque rejects null
    queue.add(root);
    boolean seenGap = false;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            seenGap = true;                           // a missing position
            continue;
        }
        if (seenGap) return false;                    // a real node after a missing position
        queue.add(node.left);
        queue.add(node.right);
    }
    return true;
}

The example tree is not complete: reading level by level gives 1, 2, 3, 4, 5, (missing), 6, and 6 comes after a gap.

Perfect: every internal node has two children and all leaves are on the same level, so every level is completely full. A perfect tree with h levels has exactly 2^h - 1 nodes, and no other tree of that height has that many, so comparing the size with 2^h - 1 is a complete test.

static boolean isPerfect(TreeNode root) {
    int h = height(root);
    return size(root) == (1L << h) - 1;
}

Balanced (height-balanced): at every node, the heights of the left and right subtrees differ by at most one. Balanced trees have height O(log n), which is what keeps search trees fast. The checker computes heights bottom-up and uses -1 to report “already unbalanced somewhere below”, so each node is visited only once.

static boolean isBalanced(TreeNode root) {
    return balancedHeight(root) != -1;
}

private static int balancedHeight(TreeNode root) {   // the height, or -1 as soon as some node is unbalanced
    if (root == null) return 0;
    int l = balancedHeight(root.left);
    if (l == -1) return -1;
    int r = balancedHeight(root.right);
    if (r == -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

The example tree is balanced: at the root the subtree heights are 3 and 2, at node 2 they are 1 and 2, at node 3 they are 0 and 1, and at node 5 they are 1 and 0.

Degenerate (skewed): every node has at most one child, so the tree is a linked list in disguise and its height equals its size. Many tree algorithms that are O(log n) on balanced trees become O(n) on these.

static boolean isDegenerate(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left != null && cur.right != null) return false;
        cur = (cur.left != null) ? cur.left : cur.right;
    }
    return true;
}

How the categories relate: every perfect tree is both full and complete; a complete tree is always balanced; a full tree need not be complete ([1, 2, 3, null, null, 4, 5] is full but has a gap); and a degenerate tree with three or more nodes is never balanced. The empty tree and a single node satisfy every definition at once.

Tree (level order) Full Complete Perfect Balanced Degenerate
[1, 2, 3, 4, 5, 6, 7] yes yes yes yes no
[1, 2, 3, 4, 5, 6] no yes no yes no
[1, 2, 3, null, null, 4, 5] yes no no yes no
the example tree no no no yes no
[1, null, 2, 3, null, null, 4] no no no no yes

Counting facts

Each level can hold at most twice as many nodes as the level above it, since each node has at most two children. Starting from one root, level i holds at most 2^i nodes.

static long maxNodesAtLevel(int level) {
    return 1L << level;
}

Adding the levels up, a tree with h levels holds at most 1 + 2 + 4 + ... + 2^(h-1) = 2^h - 1 nodes. The long return type matters: 1 << 31 already overflows an int.

static long maxNodesWithHeight(int h) {
    return (1L << h) - 1;
}

Turning this around gives the most important fact about trees: to hold n nodes you need at least ceil(log2(n + 1)) levels, and a balanced tree gets close to that bound. A million nodes fit in 20 levels, so an operation that walks one root-to-leaf path in a balanced tree does about 20 steps, while the same operation on a degenerate tree may take a million.

static int minHeight(long n) {
    int h = 0;
    while (maxNodesWithHeight(h) < n) h++;
    return h;
}

Edge cases and pitfalls