8.5 Tree Height

Tree height measures how far a tree extends downward from a node.

algorithmstreesdata-structures

8.5 Tree Height

Tree height measures how far a tree extends downward from a node. It is one of the first values you learn to compute on a tree, but it also appears inside more advanced algorithms. Balanced-tree checks, diameter computation, expression-tree evaluation cost, recursion-depth analysis, and many tree dynamic programming problems all depend on height.

The main idea is recursive: the height of a node depends on the maximum height among its children.

Problem

You need to compute the height of a tree, or the height of every subtree.

Solution

For a rooted tree represented as child lists, compute height with a postorder DFS.

package main

import "fmt"

func height(tree [][]int, node int) int {
    best := 0

    for _, child := range tree[node] {
        childHeight := height(tree, child)

        if childHeight > best {
            best = childHeight
        }
    }

    return best + 1
}

func main() {
    tree := [][]int{
        {1, 2},
        {3, 4},
        {},
        {},
        {},
    }

    fmt.Println(height(tree, 0))
}

The output is:

3

The root has height 3 when height is counted in nodes.

Some algorithms count height in edges instead. Under that convention, a leaf has height 0, and an empty child contributes -1.

func heightEdges(tree [][]int, node int) int {
    best := -1

    for _, child := range tree[node] {
        childHeight := heightEdges(tree, child)

        if childHeight > best {
            best = childHeight
        }
    }

    return best + 1
}

For the same tree, this returns:

2

Choose one convention and keep it consistent.

Discussion

There are two common definitions of height:

Convention Leaf Height Root Height in Sample
Count nodes 1 3
Count edges 0 2

Both are valid. The node-counting version is often convenient for recursive formulas because every non-empty subtree has height at least 1. The edge-counting version is common in graph theory because distance usually counts edges.

The recurrence is the same in both cases:

height(node) = 1 + max(height(child))

The only difference is the base value used for a node with no children.

For node-counting height, the maximum over an empty child list is treated as 0.

For edge-counting height, the maximum over an empty child list is treated as -1.

Computing All Heights

If you need the height of every subtree, store the result during DFS.

func allHeights(tree [][]int, root int) []int {
    heights := make([]int, len(tree))

    var dfs func(int)
    dfs = func(node int) {
        best := 0

        for _, child := range tree[node] {
            dfs(child)

            if heights[child] > best {
                best = heights[child]
            }
        }

        heights[node] = best + 1
    }

    dfs(root)
    return heights
}

For this tree:

0
├── 1
│   ├── 3
│   └── 4
└── 2

the heights are:

node 0: 3
node 1: 2
node 2: 1
node 3: 1
node 4: 1

The algorithm computes child heights before parent heights, which makes it a postorder traversal.

Undirected Trees

When the input is an undirected tree, impose a root during traversal and pass the parent.

func heightUndirected(adj [][]int, node, parent int) int {
    best := 0

    for _, next := range adj[node] {
        if next == parent {
            continue
        }

        childHeight := heightUndirected(adj, next, node)

        if childHeight > best {
            best = childHeight
        }
    }

    return best + 1
}

The parent guard prevents the recursion from walking back along the edge it just used.

This version computes height relative to the chosen root. If you choose a different root, subtree relationships change, and the height value may change as well.

Height of a Binary Tree

For pointer-based binary trees, the same recurrence becomes simpler because every node has at most two children.

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func heightBinary(root *Node) int {
    if root == nil {
        return 0
    }

    leftHeight := heightBinary(root.Left)
    rightHeight := heightBinary(root.Right)

    if leftHeight > rightHeight {
        return leftHeight + 1
    }

    return rightHeight + 1
}

Here an empty tree has height 0, and a leaf has height 1.

This convention works well for many binary-tree algorithms.

Iterative Height Computation

Recursive height computation is compact, but an iterative version is useful when the tree may be very deep.

For a rooted tree, use an explicit stack to produce a postorder sequence.

func heightIterative(tree [][]int, root int) int {
    order := []int{}
    stack := []int{root}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        order = append(order, node)

        for _, child := range tree[node] {
            stack = append(stack, child)
        }
    }

    heights := make([]int, len(tree))

    for i := len(order) - 1; i >= 0; i-- {
        node := order[i]
        best := 0

        for _, child := range tree[node] {
            if heights[child] > best {
                best = heights[child]
            }
        }

        heights[node] = best + 1
    }

    return heights[root]
}

The first pass records a traversal order. Reversing that order ensures children are processed before parents.

This method avoids recursive call-stack growth.

Using Height to Check Balance

A binary tree is height-balanced if the left and right subtrees of every node differ in height by at most one.

A direct implementation computes height repeatedly and may become quadratic.

func isBalancedSlow(root *Node) bool {
    if root == nil {
        return true
    }

    leftHeight := heightBinary(root.Left)
    rightHeight := heightBinary(root.Right)

    if abs(leftHeight-rightHeight) > 1 {
        return false
    }

    return isBalancedSlow(root.Left) && isBalancedSlow(root.Right)
}

The problem is that heightBinary is called again for the same subtrees many times.

A better implementation combines height computation and balance checking in one traversal.

func balancedHeight(root *Node) (int, bool) {
    if root == nil {
        return 0, true
    }

    leftHeight, leftOK := balancedHeight(root.Left)
    if !leftOK {
        return 0, false
    }

    rightHeight, rightOK := balancedHeight(root.Right)
    if !rightOK {
        return 0, false
    }

    if abs(leftHeight-rightHeight) > 1 {
        return 0, false
    }

    if leftHeight > rightHeight {
        return leftHeight + 1, true
    }

    return rightHeight + 1, true
}

func isBalanced(root *Node) bool {
    _, ok := balancedHeight(root)
    return ok
}

func abs(x int) int {
    if x < 0 {
        return -x
    }

    return x
}

This version visits every node once.

Complexity Analysis

For a tree with n nodes:

Algorithm Time Extra Space
Recursive height O(n) O(h)
Store all heights O(n) O(n)
Iterative height O(n) O(n)
Slow balance check O(n²) worst case O(h)
One-pass balance check O(n) O(h)

Here h is the height of the tree.

For a balanced tree, h = O(log n). For a degenerate tree, h = O(n).

Common Mistakes

The most common mistake is mixing height conventions. If one function treats a leaf as height 1 and another treats it as height 0, later formulas will be off by one.

Another mistake is computing height repeatedly inside a larger recursive algorithm. When a result is needed more than once, return it alongside the other information or store it in an array.

A third mistake is assuming height is a property of an unrooted tree without specifying the root. In an undirected tree, height depends on which node you choose as the root.

Takeaway

Tree height is a postorder computation. Each node waits for its children, takes the maximum child height, and adds one. The algorithm is simple, but the convention matters: decide whether height counts nodes or edges, then use that convention everywhere. When height is part of a larger algorithm, compute it in the same traversal instead of recomputing it from scratch.