Binary tree fundamentals

CLRS says the height of an empty tree is 0. Some AVL textbooks say it's -1. CMU's 15-121 lecture notes say height is "edges from a node to the deepest leaf"; OpenDSA says height is "number of levels." All four are correct in their own framing. Pick the wrong one halfway through your code and your height(root) for [3, 9, 20, null, null, 15, 7] returns 2 instead of 3, and you spend the rest of the interview convinced the bug is somewhere else.

Part 6 spends eleven chapters on trees and heaps. Every one of them assumes you know exactly what height means in this book. So this chapter pins the terminology, defines the two physical representations a binary tree can take, and sets up the one-paragraph recursion template every later chapter will lift and bend. Treat it as the glossary you come back to whenever a future chapter says "see 6.0's definition of height."

What a binary tree is#

A binary tree is either empty, or it's a node holding a value plus two binary trees called its left and right children. That is the entire structural definition. The recursion in the definition is not a teaching trick; it's the data structure. Whenever you see a binary-tree problem and reach for recursion, you're reaching for the shape that's already in the type.^[1]

A node with at least one child is internal. A node with no children is a leaf. The single node with no parent is the root.

The path from the root down to any node has a length, and that length is the node's depth. The longest path going the other direction, from a node down to the deepest descendant leaf, is the node's height. The tree's height is the height of its root.

Tree of height 3. Node 1 is the root at depth 0; nodes 3, 5, 6, 7 are leaves; every node carries both a depth (distance down from root) and a height (distance down to its deepest descendant). Node 4's height is 1 because the longest root-to-leaf path inside its subtree has length 1.

This book uses one convention everywhere: heights are measured in nodes-on-the-path, not edges. The empty tree has height 0. A leaf has height 1. The recurrence is height(node) = 1 + max(height(left), height(right)) with height(null) = 0. This matches the LC 104 problem statement, CLRS §10.4, and OpenDSA Ch 7.2.^[2][1:1] AVL chapters elsewhere on the internet often switch to height-in-edges (where the empty tree has height -1); we explicitly do not, except inside chapter 6.6 AVL trees, where the textbook proof shape needs it. When we get there, we'll annotate the convention switch.

Three shape restrictions worth naming#

Not every binary tree is the same. Three named shapes show up in algorithm proofs and in interview questions, and getting the definitions right matters because they aren't synonyms.

A full tree is one where every internal node has exactly two children. No node has just a left child or just a right child.

A complete tree is one where every level is filled left-to-right, with a possibly-incomplete bottom level that still fills from the left. This is the shape a binary heap maintains, and it's the reason heap operations can be expressed on a flat array.

A perfect tree is both full and complete, with all leaves at the same depth. A perfect tree of height h has exactly 2^h - 1 nodes.

Three named shapes. Full means every internal node has two children. Complete means every level is filled left to right. Perfect is both. Full plus Complete does not imply Perfect; the middle tree above is Complete but not Full, and the leftmost is Full but not Complete.^[3]

A tree is balanced in the LC sense (and the AVL sense) if every node's left and right subtree heights differ by at most 1. Balanced does not imply perfect; balanced does not imply complete. A balanced tree can have any of these shapes or none of them. The LC 110 problem is the canonical "is this tree balanced?" check.

Two ways to store a tree in memory#

The same logical tree can live in your program in two different physical representations. Picking the right one is the first design choice in any tree problem.

Pointer-backed: nodes that hold pointers to nodes#

The default for every problem this part covers except heaps. Each node is an object with a value and two pointers (or references) to its children. Missing children are null.

@dataclass
class TreeNode:
    val: int = 0
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None

In Java, TreeNode is a class with int val, TreeNode left, TreeNode right. In C++ it's a struct with raw pointers and explicit nullptr. In Go it's a struct with *TreeNode fields. LeetCode's tree problems all hand you a pointer-backed root; the level-order array in the prompt ([3,9,20,null,null,15,7]) is the input format the judge uses to serialize the tree, not the in-memory shape.^[4]

Pointer-backed wins when the tree is sparse, when nodes get inserted and deleted at runtime, and when traversal naturally follows the pointer structure. The cost is that each node carries a 16- or 24-byte pointer overhead on top of its payload, and the children sit wherever the allocator put them, which is usually nowhere near the parent in cache.

Array-backed: nodes addressed by index arithmetic#

When the tree is complete (every level filled left-to-right), the pointers are redundant. Number the nodes level-by-level starting at index 0 for the root. Then for any node at index i:

• the parent lives at index (i - 1) / 2 (integer division)
• the left child lives at index 2*i + 1
• the right child lives at index 2*i + 2

A complete tree stored in a flat array [50, 30, 40, 10, 20, 15, 25]. The pointers are computed, not stored: parent of index 4 is (4-1)/2 = 1, children of index 1 are 2*1+1 = 3 and 2*1+2 = 4. CLRS §6.1 uses indices starting at 1 with 2*i and 2*i+1; modern code uses 0-indexing with 2*i+1 and 2*i+2.^[5]

Array-backed wins when the tree is dense and you only ever push to the next free slot or pop from the last filled slot. That's exactly the heap contract. Chapter 6.4 will use this representation in earnest. For everything else in Part 6 — BSTs, AVL trees, tries, segment trees — you want pointers, because their balance properties don't keep the tree complete.

The post-order recursion template#

Here's the shape that solves almost every binary-tree problem in Part 6. The signature problem is LC 110, Balanced Binary Tree: given a tree, return true if every node's left and right subtree heights differ by at most 1.^[6]

The naive instinct is to write is_balanced(node) directly: at each node, compute height(left), compute height(right), check the difference, recurse on both children. It works. It's also slower than it needs to be. Every node ends up paying for height computations of its descendants twice: once when the descendant is visited as a parent, once again when its ancestor recomputes the height through it.

The fix is to compute the height once, and to make the height function carry a second piece of information: a sentinel value meaning "stop, this subtree is unbalanced." Heights are non-negative, so -1 is a value the natural domain can never produce. Return it from any subtree that fails the balance check, and let it propagate.

# LC 110. Balanced Binary Tree
"""LC 110 Balanced Binary Tree, height-or-sentinel post-order recursion."""

from dataclasses import dataclass
from typing import Optional


@dataclass
class TreeNode:
    val: int = 0
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None


def is_balanced(root: Optional[TreeNode]) -> bool:
    """Return True iff every node's left/right subtree heights differ by <= 1."""

    def height(node: Optional[TreeNode]) -> int:
        # Returns subtree height, or -1 if any descendant is unbalanced.
        if node is None:
            return 0
        lh = height(node.left)
        if lh == -1:
            return -1
        rh = height(node.right)
        if rh == -1:
            return -1
        if abs(lh - rh) > 1:
            return -1
        return 1 + max(lh, rh)

    return height(root) != -1

/* LC 110 Balanced Binary Tree, height-or-sentinel post-order recursion. */
public final class Sol {

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

    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int lh = height(node.left);
        if (lh == -1) return -1;
        int rh = height(node.right);
        if (rh == -1) return -1;
        if (Math.abs(lh - rh) > 1) return -1;
        return 1 + Math.max(lh, rh);
    }
}

// LC 110. Balanced Binary Tree
// LC 110 Balanced Binary Tree, height-or-sentinel post-order recursion.
#include <algorithm>
#include <cstdlib>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }

private:
    int height(TreeNode* node) {
        if (node == nullptr) return 0;
        int lh = height(node->left);
        if (lh == -1) return -1;
        int rh = height(node->right);
        if (rh == -1) return -1;
        if (std::abs(lh - rh) > 1) return -1;
        return 1 + std::max(lh, rh);
    }
};

// LC 110. Balanced Binary Tree
//.
// LC 110 Balanced Binary Tree, height-or-sentinel post-order recursion.
package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isBalanced(root *TreeNode) bool {
	return height(root) != -1
}

func height(node *TreeNode) int {
	if node == nil {
		return 0
	}
	lh := height(node.Left)
	if lh == -1 {
		return -1
	}
	rh := height(node.Right)
	if rh == -1 {
		return -1
	}
	diff := lh - rh
	if diff < 0 {
		diff = -diff
	}
	if diff > 1 {
		return -1
	}
	if lh > rh {
		return 1 + lh
	}
	return 1 + rh
}

Three properties make the template reusable. The base case node is None returns an identity value (0) so the parent's combine step has well-defined operands; without it, every recursion needs ad-hoc null-checks at the call site. The post-order ordering, left first then right then combine at the current node, is what lets the parent inspect both children's results before deciding anything; pre-order or in-order would not. And the sentinel collapses two return modes into one channel, which is the move you'll repeat in BST validation, AVL rebalance triggers, and tree DP.

What changes for related problems#

The same template, with one or two lines swapped, solves every other tree-recursion problem on the chapter ladder.

LC 104, Maximum Depth of Binary Tree. Drop the sentinel; the recurrence is the height function with no abort condition.^[7]

def max_depth(node):
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

LC 236, Lowest Common Ancestor of a Binary Tree. The return type changes from int to TreeNode. At each node, recurse into both subtrees; if both calls return non-null, this node is the LCA; otherwise propagate whichever side returned a non-null result.^[8]

def lowest_common_ancestor(node, p, q):
    if node is None or node is p or node is q:
        return node
    left = lowest_common_ancestor(node.left, p, q)
    right = lowest_common_ancestor(node.right, p, q)
    if left and right:
        return node                           # both targets in different subtrees
    return left if left else right            # propagate the one we found

The decision at each node is exactly the same shape as the height-or-sentinel: post-order, combine at the parent. Only the carrier — what each call returns — has changed. Sentinel integers, node references, tuples of multiple facts, mutable globals threaded through the helper: every variant in the rest of Part 6 swaps the carrier and keeps the post-order spine.

What it actually costs#

Two of those rows deserve a closer look.

The naive solution is not O(n²)#

Interview-prep editorials commonly report the naive height-twice solution as O(n²). It isn't. The early-exit if abs(left - right) > 1: return False short-circuits the second recursive call whenever one subtree has already failed, and the recursive structure forces the depths in subsequent calls to depend on each other. A community-vetted Stack Overflow analysis from February 2026 constructs the worst-case input shape (right subtrees as paths to a fixed depth) and proves the algorithm is O(n √n), tight.^[9:1] The proof reduces to: if K is the longest nested-left-recurse chain on the worst path and N is the total node count, then N ≥ c₁ · K² and total runtime is bounded by c₂ · K · N ≤ c₂ · N · √(N/c₁).

This matters in the room. State the bound as O(n √n) when you walk an interviewer through the naive version, and follow with "but the optimal is O(n) using a sentinel return value." Every interviewer who knows the tight bound will notice; the ones who don't will at least learn something.

Recursion depth on skewed inputs#

LC 110's input cap is 5,000 nodes. CPython's default sys.getrecursionlimit() is 1,000.^[10:1] A balanced 5,000-node tree has height around 13 and recurses 13 levels deep, which is fine. A skewed 5,000-node left-leaning chain recurses 5,000 levels deep and raises RecursionError. The judge tests both shapes.

The fix is one line at the top of the Python solution:

import sys
sys.setrecursionlimit(10**6)

Java, C++, and Go don't need this; their default thread stacks tolerate the depth. The handbook's project-wide policy is to set the limit once at module top-level for any Python solution that recurses on tree height. LC 110 itself is safe with or without the call only when the judge feeds you a balanced input; the moment you graduate to Morris traversal at 6.2 or tree DP at 9.13, the call is non-negotiable.

Five places this trips people up#

Problem ladder#

CORE (solve all three to claim chapter mastery)#

• LC 110 — Balanced Binary Tree [Easy] • tree-recursion-divide-and-conquer ★
• LC 104 — Maximum Depth of Binary Tree [Easy] • tree-recursion-divide-and-conquer
• LC 236 — Lowest Common Ancestor of a Binary Tree [Medium] • tree-recursion-with-combine-flags

STRETCH (optional)#

• LC 543 — Diameter of Binary Tree [Easy] • tree-recursion-with-global-state
• LC 100 — Same Tree [Easy] • tree-recursion-on-two-trees

LC 543 and LC 100 are STRETCH because they extend the post-order template in two specific directions: LC 543 threads a mutable global through the height helper (the shape that scales up to LC 124 Maximum Path Sum in tree DP), and LC 100 walks two trees in lockstep (the shape that scales up to BST structural validation at chapter 6.5).

Where this leads#

The post-order template is the spine of Part 6. Tree traversals animates the recursion in motion and introduces the iterative-with-stack equivalents that Morris traversal then replaces with O(1) extra space. Heaps reuses the array-backed representation introduced above; BSTs uses the two-tree-lockstep shape from LC 100 to validate the BST ordering invariant; AVL trees lifts the height-or-sentinel idea from LC 110 to detect rebalancing triggers. The Hard generalizations live further out: LC 124 Maximum Path Sum belongs to Tree DP and LC 297 Serialize and Deserialize Binary Tree belongs to the next chapter on traversals.

References#