Loading learning content...
In the previous page, we measured depth—how far a node is from the root, looking upward through ancestor relationships. Now we turn our attention in the opposite direction: height measures how far a node can reach downward through its descendant relationships.
If depth answers "How far am I from the top?", then height answers "How far can I go to the bottom?" This seemingly simple distinction carries profound implications for tree algorithms, memory usage patterns, and performance analysis.
By the end of this page, you will understand the formal definition of node height, master the recursive computation pattern for height, distinguish between node height and tree height, and recognize how height impacts algorithm design and complexity analysis.
Height measures how far a node is from the most distant leaf in its subtree. Formally:
The height of a node is the number of edges on the longest path from that node to any leaf descendant.
This definition elegantly captures the concept of "downward reach"—how deep the subtree rooted at this node extends.
While depth looks upward (from node to root), height looks downward (from node to deepest leaf). They measure the same concept—distance in the tree—but in opposite directions. A node's depth plus the height of the tree's root gives you the tree's total "span," but depth and height of a single node generally differ.
Key properties of height:
Leaf nodes have height 0 — A leaf has no children, so the longest path to a leaf descendant is zero edges (the leaf itself).
Height is non-negative — No node can have negative height.
Height of internal nodes depends on children — A non-leaf node's height is 1 + the maximum height among its children.
Height is computed bottom-up — Unlike depth (computable from root), height requires knowledge of the entire subtree below.
The root's height equals the tree's height — The tree's overall height is defined as the height of its root node.
| Node Type | Height | Reasoning |
|---|---|---|
| Leaf node | 0 | No children; path to leaf is empty |
| Parent of only leaves | 1 | One edge to reach any leaf child |
| Grandparent of leaves | 2 | Two edges to reach leaf grandchildren |
| Root (if tree height is h) | h | Longest path in entire tree |
Understanding height becomes intuitive when we annotate a tree with height values. Consider the following binary tree, where each node shows its height in parentheses:
A (h=3) / \ / \ B (h=2) C (h=1) / \ \ D (h=1) E (h=0) F (h=0) / G (h=0) Height Breakdown (computed bottom-up): ───────────────────────────────────────── G: height = 0 (leaf) E: height = 0 (leaf) F: height = 0 (leaf) D: height = 1 (1 + max(height(G)) = 1 + 0 = 1) C: height = 1 (1 + max(height(F)) = 1 + 0 = 1) B: height = 2 (1 + max(height(D), height(E)) = 1 + max(1,0) = 2) A: height = 3 (1 + max(height(B), height(C)) = 1 + max(2,1) = 3) ───────────────────────────────────────── Longest paths from each node to a leaf: • From A: A → B → D → G (3 edges) • From B: B → D → G (2 edges) • From C: C → F (1 edge) • From D: D → G (1 edge) • From E, F, G: ∅ (0 edges - already leaves)Observations from the visualization:
Leaves have height 0 — Nodes G, E, and F are all leaves with height 0.
Height propagates upward — Each internal node's height is determined by its tallest child. Node B takes its height from D (the taller child) plus one.
Siblings can have different heights — B has height 2 while C has height 1, despite both being children of A. Height depends on the subtree below, not the position in the tree.
The root captures tree height — The root A has height 3, which is the tree's overall height (longest root-to-leaf path).
Height and depth are independent — Node C has depth 1 and height 1 (coincidentally equal). Node B has depth 1 but height 2. There's no fixed relationship between a node's depth and height.
Think of height like the organizational depth below a manager. A CEO's "height" is the number of management levels below them—the longest chain from CEO to an individual contributor. A team lead with only individual contributors reporting to them has height 1. An individual contributor (no reports) has height 0. The CEO's height equals the organization's total depth.
Height has a beautifully recursive definition that mirrors the recursive structure of trees themselves:
height(node) = 0 if node is a leaf
height(node) = 1 + max(height(child) for each child) otherwise
This recursive definition is not just mathematically elegant—it directly translates into an efficient algorithm. Let's explore why this works and how to implement it.
The subtree property: Every node in a tree can be viewed as the root of its own subtree. The height of a node is really asking: "What is the height of the subtree rooted at this node?"
The composition insight: The height of a subtree equals the height of its tallest child-subtree plus one (for the edge connecting parent to child).
Natural bottom-up computation: Unlike depth (which can be computed top-down), height requires knowing the heights of descendants first. Recursion naturally handles this—the recursive calls complete for children before the parent's height is computed.
This is a classic example of a post-order computation pattern: we need information from children before we can compute a result for the parent.
Height computation follows a post-order pattern: visit children recursively, then compute the parent's value using the children's results. This pattern appears in many tree algorithms: computing subtree sizes, evaluating expression trees, computing balance factors, and more. Recognizing this pattern is key to designing efficient tree algorithms.
The recursive definition of height translates directly into clean, efficient code. Here's the implementation for binary trees (easily extensible to n-ary trees):
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
interface BinaryTreeNode<T> { value: T; left: BinaryTreeNode<T> | null; right: BinaryTreeNode<T> | null;} /** * Computes the height of a node (subtree rooted at this node). * * Definition: The height is the number of edges on the longest path * from this node to any leaf descendant. * * Time Complexity: O(n) where n is the number of nodes in the subtree * - Each node is visited exactly once * Space Complexity: O(h) where h is the height of the subtree * - Due to recursive call stack * * @param node - The root of the subtree to measure * @returns Height of the subtree (-1 for null/empty) */function computeHeight<T>(node: BinaryTreeNode<T> | null): number { // Base case: null subtree has height -1 // (This makes a single node have height 0, which is correct) if (node === null) { return -1; } // Recursive case: height = 1 + max of children's heights const leftHeight = computeHeight(node.left); const rightHeight = computeHeight(node.right); return 1 + Math.max(leftHeight, rightHeight);} /** * Alternative: Height using 0 for null (different convention). * With this convention, a single leaf node has height 1. * Use whichever convention your codebase follows. */function computeHeightAlt<T>(node: BinaryTreeNode<T> | null): number { if (node === null) { return 0; // Empty tree has height 0 } const leftHeight = computeHeightAlt(node.left); const rightHeight = computeHeightAlt(node.right); return 1 + Math.max(leftHeight, rightHeight); // Note: With this convention, leaf height = 1, not 0} // Example usage and verificationfunction demonstrateHeightComputation() { // Build tree: A // / \ // B C // / // D const nodeD: BinaryTreeNode<string> = { value: 'D', left: null, right: null }; const nodeB: BinaryTreeNode<string> = { value: 'B', left: nodeD, right: null }; const nodeC: BinaryTreeNode<string> = { value: 'C', left: null, right: null }; const nodeA: BinaryTreeNode<string> = { value: 'A', left: nodeB, right: nodeC }; console.log(`Height of D: ${computeHeight(nodeD)}`); // 0 (leaf) console.log(`Height of C: ${computeHeight(nodeC)}`); // 0 (leaf) console.log(`Height of B: ${computeHeight(nodeB)}`); // 1 console.log(`Height of A: ${computeHeight(nodeA)}`); // 2}There are two common conventions for empty/null nodes: returning -1 (our choice, making leaves have height 0) or returning 0 (making leaves have height 1). Both are valid; just be consistent within your codebase. The -1 convention aligns with counting edges, while the 0 convention counts levels.
The height concept extends naturally to n-ary trees (trees where nodes can have any number of children). The definition remains the same: longest path to any leaf descendant.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
interface NaryTreeNode<T> { value: T; children: NaryTreeNode<T>[];} /** * Computes height of an n-ary tree node. * * The logic is the same as binary trees, but we iterate over all children * instead of just left and right. * * Time Complexity: O(n) - visits each node once * Space Complexity: O(h) - recursive call stack */function computeNaryHeight<T>(node: NaryTreeNode<T> | null): number { // Base case: null node if (node === null) { return -1; } // Leaf node (no children) if (node.children.length === 0) { return 0; } // Internal node: 1 + max height among all children let maxChildHeight = -1; for (const child of node.children) { const childHeight = computeNaryHeight(child); maxChildHeight = Math.max(maxChildHeight, childHeight); } return 1 + maxChildHeight;} /** * Concise version using reduce. */function computeNaryHeightConcise<T>(node: NaryTreeNode<T> | null): number { if (node === null) return -1; if (node.children.length === 0) return 0; return 1 + Math.max( ...node.children.map(child => computeNaryHeightConcise(child)) );} // Example: File system directory depthinterface FileSystemNode { name: string; isDirectory: boolean; children: FileSystemNode[];} function computeMaxDirectoryDepth(root: FileSystemNode): number { if (!root.isDirectory || root.children.length === 0) { return 0; } let maxChildDepth = 0; for (const child of root.children) { if (child.isDirectory) { maxChildDepth = Math.max( maxChildDepth, computeMaxDirectoryDepth(child) ); } } return 1 + maxChildDepth;}Height computation appears in many real applications: measuring directory nesting depth in file systems, computing the depth of nested UI components, analyzing dependency tree depth in package managers, measuring the depth of XML/JSON hierarchies, and evaluating expression tree complexity.
While recursion is the natural approach for height computation, sometimes we need an iterative solution—particularly when tree depth could exceed stack limits. The key insight is that we can use level-order traversal (BFS) and count levels.
The idea is simple: traverse the tree level by level using a queue. Count how many levels we traverse. The height is (number of levels - 1) when using the edge-counting convention.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
/** * Computes tree height iteratively using level-order traversal. * * This approach is useful when: * 1. Tree depth might exceed stack limits * 2. You're already doing BFS for another purpose * 3. You want to avoid recursion overhead * * Time Complexity: O(n) - visits each node once * Space Complexity: O(w) - where w is max tree width (queue size) */function computeHeightIterative<T>(root: BinaryTreeNode<T> | null): number { if (root === null) { return -1; } const queue: BinaryTreeNode<T>[] = [root]; let height = -1; // Start at -1; first level brings it to 0 while (queue.length > 0) { height++; // Entering a new level const levelSize = queue.length; // Process all nodes at current level for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; // Add children to queue (next level) if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } return height;} /** * Alternative: Use depth markers in queue. * Some find this approach more intuitive. */function computeHeightWithMarkers<T>(root: BinaryTreeNode<T> | null): number { if (root === null) return -1; interface QueueItem { node: BinaryTreeNode<T>; depth: number; } const queue: QueueItem[] = [{ node: root, depth: 0 }]; let maxHeight = 0; while (queue.length > 0) { const { node, depth } = queue.shift()!; maxHeight = Math.max(maxHeight, depth); if (node.left) { queue.push({ node: node.left, depth: depth + 1 }); } if (node.right) { queue.push({ node: node.right, depth: depth + 1 }); } } return maxHeight;}Height is one of the most important metrics for analyzing tree performance. Understanding how height relates to tree structure and operation efficiency is crucial for algorithm analysis.
Different tree structures guarantee different height bounds:
| Tree Type | Height Bound | Implication |
|---|---|---|
| Any tree with n nodes | 0 to n-1 | No guarantee |
| Complete binary tree | ⌊log₂n⌋ | Optimal height |
| AVL tree | < 1.44 × log₂(n+2) | Near-optimal |
| Red-black tree | ≤ 2 × log₂(n+1) | Guaranteed logarithmic |
| BST (unbalanced) | 0 to n-1 | Depends on insertion order |
These bounds directly translate to operation time bounds, since most tree operations depend on height.
In balanced trees like AVL, we track the balance factor of each node:
balance_factor(node) = height(left_child) - height(right_child)
A balanced tree maintains |balance_factor| ≤ 1 for every node. This constraint ensures the tree remains approximately balanced, keeping height logarithmic.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
interface AVLNode<T> { value: T; left: AVLNode<T> | null; right: AVLNode<T> | null; height: number; // Cache height for O(1) access} /** * Computes the balance factor of a node. * Balance factor = height(left) - height(right) * * A balanced node has balance factor in {-1, 0, 1} */function getBalanceFactor<T>(node: AVLNode<T> | null): number { if (node === null) return 0; const leftHeight = node.left?.height ?? -1; const rightHeight = node.right?.height ?? -1; return leftHeight - rightHeight;} /** * Checks if a subtree is height-balanced (AVL property). * Returns the height if balanced, or -Infinity if unbalanced. */function checkBalance<T>(node: BinaryTreeNode<T> | null): number { if (node === null) return -1; const leftHeight = checkBalance(node.left); if (leftHeight === -Infinity) return -Infinity; // Left unbalanced const rightHeight = checkBalance(node.right); if (rightHeight === -Infinity) return -Infinity; // Right unbalanced const balanceFactor = leftHeight - rightHeight; if (Math.abs(balanceFactor) > 1) { return -Infinity; // This node is unbalanced } return 1 + Math.max(leftHeight, rightHeight);} function isBalanced<T>(root: BinaryTreeNode<T> | null): boolean { return checkBalance(root) !== -Infinity;}In self-balancing trees like AVL, we typically store height as a field in each node rather than recomputing it. This makes balance factor computation O(1) instead of O(n). The height field is updated during insertions and deletions, adding only O(1) work per node on the affected path.
Height computation is a building block for many classic tree problems. Here are patterns you'll encounter frequently:
The diameter is the longest path between any two nodes (may or may not pass through the root). This is elegantly solved by computing heights while tracking the maximum path.
12345678910111213141516171819202122232425262728
/** * Finds the diameter of a binary tree in O(n) time. * * Key insight: For each node, the longest path through that node is: * height(left) + height(right) + 2 (the "+2" for edges to children) * * The diameter is the maximum of all such paths. */function diameterOfBinaryTree<T>(root: BinaryTreeNode<T> | null): number { let maxDiameter = 0; function computeHeightAndUpdateDiameter(node: BinaryTreeNode<T> | null): number { if (node === null) return -1; const leftHeight = computeHeightAndUpdateDiameter(node.left); const rightHeight = computeHeightAndUpdateDiameter(node.right); // Path through this node: left subtree height + right subtree height + 2 const pathThroughNode = leftHeight + rightHeight + 2; maxDiameter = Math.max(maxDiameter, pathThroughNode); // Return height for parent's computation return 1 + Math.max(leftHeight, rightHeight); } computeHeightAndUpdateDiameter(root); return maxDiameter;}Determine if no node has subtrees differing in height by more than 1. We solve this in a single pass by combining height computation with balance checking:
1234567891011121314151617181920212223242526272829
/** * Checks if a binary tree is height-balanced in O(n) time. * * A height-balanced tree has the property that for every node, * the heights of its left and right subtrees differ by at most 1. */function isHeightBalanced<T>(root: BinaryTreeNode<T> | null): boolean { /** * Returns the height if balanced, or -Infinity if any subtree is unbalanced. * This "early exit" pattern avoids unnecessary computation. */ function checkBalancedHeight(node: BinaryTreeNode<T> | null): number { if (node === null) return -1; const leftHeight = checkBalancedHeight(node.left); if (leftHeight === -Infinity) return -Infinity; const rightHeight = checkBalancedHeight(node.right); if (rightHeight === -Infinity) return -Infinity; if (Math.abs(leftHeight - rightHeight) > 1) { return -Infinity; // Unbalanced at this node } return 1 + Math.max(leftHeight, rightHeight); } return checkBalancedHeight(root) !== -Infinity;}Find the shortest path from root to any leaf. This is the "opposite" of height in some sense:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
/** * Finds the minimum depth (root to nearest leaf). * * Note: A node with only one child is NOT a leaf! * We must be careful not to count paths that end at non-leaves. */function minDepthToLeaf<T>(root: BinaryTreeNode<T> | null): number { if (root === null) return -1; // Leaf node if (root.left === null && root.right === null) { return 0; } // Only left child exists - must go left if (root.right === null) { return 1 + minDepthToLeaf(root.left); } // Only right child exists - must go right if (root.left === null) { return 1 + minDepthToLeaf(root.right); } // Both children exist - take minimum return 1 + Math.min( minDepthToLeaf(root.left), minDepthToLeaf(root.right) );} /** * BFS approach - often faster for unbalanced trees. * Stops as soon as we find a leaf. */function minDepthBFS<T>(root: BinaryTreeNode<T> | null): number { if (root === null) return -1; const queue: Array<{ node: BinaryTreeNode<T>; depth: number }> = [ { node: root, depth: 0 } ]; while (queue.length > 0) { const { node, depth } = queue.shift()!; // First leaf we encounter is at minimum depth if (node.left === null && node.right === null) { return depth; } if (node.left) queue.push({ node: node.left, depth: depth + 1 }); if (node.right) queue.push({ node: node.right, depth: depth + 1 }); } return -1; // Should never reach here for non-empty tree}We've thoroughly explored the concept of node height—the downward companion to depth that measures a node's reach to its leaf descendants. Let's consolidate the key insights:
What's next:
With depth (upward) and height (of individual nodes) understood, we'll next examine tree height as a whole—the height of the root node. This measurement is so fundamental to tree analysis that it warrants dedicated study, including its relationship to node count, traversal complexity, and the critical distinction between balanced and unbalanced trees.
You now understand how height measures a node's downward reach, can compute height recursively and iteratively, and recognize height's role in balance analysis and tree algorithms. This complements your understanding of depth, giving you a complete picture of node positioning in tree structures.