Height of a Tree

March 2026 · 6 min read

What Is Tree Height?

The height of a tree is the length of the longest path from the root to any leaf. Equivalently, it's the number of edges on that path. A single-node tree has height 0, and an empty tree has height −1 by convention.

This is one of the most fundamental tree quantities, it appears in the analysis of nearly every tree operation. BST search is O(h), AVL rebalancing triggers at height imbalance, and tree traversal stack depth equals h.

The Recursive Insight

Tree height has a beautiful recursive structure. The height of any node is:

Why does this work? The longest path from a node to a leaf must go through either its left subtree or its right subtree. We take the max of both, then add 1 for the edge from the node to whichever child leads to the deeper subtree.

Base case: When we reach a null pointer (past a leaf), we return −1. This way, a leaf node computes 1 + max(-1, -1) = 0, which is correct, a leaf has height 0.

Why Bottom-Up?

Notice the computation flows bottom-up: we can't know the height of a node until we know the heights of both its children. This means the recursion fully descends to the leaves first, then the answers propagate upward. This bottom-up pattern recurs throughout tree algorithms (diameter, balance checking, subtree sums).

The Code

int height(TreeNode* node) {
    if (!node) return -1;           // base case: empty subtree
    int leftH  = height(node->left);  // recurse left
    int rightH = height(node->right); // recurse right
    return 1 + std::max(leftH, rightH);
}

Time: O(n), we visit every node exactly once.
Space: O(h), recursion stack depth equals the tree height.

Common Pitfall: height(null) = 0 vs -1

Some implementations define height(null) = 0 instead of −1, which counts nodes on the longest path rather than edges. Both conventions are valid, but they give different numbers: a single-node tree has height 0 (by edges) or 1 (by nodes). Be consistent, and when solving interview problems, clarify which convention is expected.

Iterative Alternative (BFS)

You can also compute height using level-order (BFS) traversal. Process the tree level by level; the number of levels minus 1 is the height:

int heightBFS(TreeNode* root) {
    if (!root) return -1;
    std::queue<TreeNode*> q;
    q.push(root);
    int height = -1;
    while (!q.empty()) {
        height++;
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            auto* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return height;
}

This uses O(w) space where w is the maximum width of the tree (up to n/2 for a complete tree), compared to O(h) for the recursive version. For balanced trees, the recursive version is more space-efficient.