Find the Height of a Binary Tree

Given the root of a binary tree, return its height: the number of edges on the longest path from the root down to a leaf. A single node has height 0, and an empty tree has height -1.

Example

Text

Values inserted: 6, 4, 9, 2, 5, 12, 10
Output: 3   (6 -> 9 -> 12 -> 10)

graph TB
    a["6 (depth 0)"] --> b["4 (depth 1)"]
    a --> c["9 (depth 1)"]
    b --> d["2 (depth 2)"]
    b --> e["5 (depth 2)"]
    c --> f["12 (depth 2)"]
    f --> g["10 (depth 3)"]

LeetCode's "Maximum Depth of Binary Tree" (104) counts nodes instead of edges. Its answer is this height plus one.

Recursive: post-order

The height of a tree is one more than the height of its taller subtree:

Text

height(empty) = -1
height(node)  = 1 + max(height(left), height(right))

With the empty tree at -1, a leaf gets 1 + max(-1, -1) = 0, as the definition requires. This is a post-order computation: both children's heights are needed before the node's height.

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. The fields are mutable, so no wrapper type is needed.

Walkthrough (computed bottom-up):

node	left height	right height	height
2, 5, 10 (leaves)	-1	-1	0
12	0 (10)	-1	1
4	0 (2)	0 (5)	1
9	-1	1 (12)	2
6	1 (4)	2 (9)	3

Java

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

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

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

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 12, 10);
        System.out.println(height(root) + " " + height(fromValues(1)) + " " + height(null));
    }
}

Output

3 0 -1

Time: O(n): every node is visited once. Space: O(h) for the recursion. For a degenerate tree (one built from sorted input, which is really a linked list) that is O(n), and a very deep tree can overflow the call stack.

Iterative: count levels with BFS

Process the tree one level at a time with a queue. The number of levels minus one is the height (in edges). ArrayDeque is a double-ended queue backed by a resizable array. It is the standard queue in Java and rejects null, so only non-null nodes are added.

Java

import java.util.ArrayDeque;
import java.util.Queue;

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

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static int height(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        int levels = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) { // exactly the nodes of this level
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels++;
        }
        return levels - 1;
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 12, 10);
        int[] sorted = new int[10_000];
        for (int i = 0; i < sorted.length; i++) sorted[i] = i + 1;
        TreeNode skewed = fromValues(sorted);
        System.out.println(height(root) + " " + height(null) + " " + height(skewed));
    }
}

Output

3 -1 9999

Time: O(n). Space: O(w), where w is the number of nodes in the widest level: up to about n/2 for a complete tree, and 1 for a skewed one.

Both approaches have the same time complexity. BFS walks the 10,000-node skewed tree without recursing.

Deep trees and the call stack

Each recursive call uses a stack frame, and the thread stack has a fixed size. A skewed tree hundreds of thousands of nodes deep can make the recursive height throw StackOverflowError, while the BFS version only grows its queue on the heap. Interview inputs rarely get that deep, but when they might, use the iterative version or an explicit stack. The garbage collector reclaims unreachable nodes, so the lesson needs no cleanup code.

Edge cases

Empty tree: -1 (or 0 if counting nodes).
Single node: 0.
Skewed tree: n - 1.