Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Find the height of a rooted tree

Use when: you have a rooted tree and need its height, the length of the longest root-to-leaf path

Goal: the height as one number, plus which leaf or leaves actually achieve it

Taught in Rooted trees and rooted-tree terminology

Quick recipe

  1. Find every leaf
  2. Trace each leaf back to the root, counting edges
  3. The height is the largest level found
  1. 1

    Scan every vertex and check whether it has any children listed; a vertex with none is a leaf, by this section's rooted-tree definition.

    Example

    In the tree above, B, D, E, and F have no children, so they're the leaves. R, A, and C each have at least one child, so none of them is a leaf.

    • the tree has only the root, with no other vertices at all — the root is the tree's only leaf, and the height is 0 by convention.
    • the tree has at least one vertex besides the root — continue to Step 2 with the leaves just found.

    Why: height is defined as the longest root-to-leaf path, so only a leaf can ever be the far end of one.

  2. 2

    Walk from the leaf up through its parent, then its parent's parent, and so on until reaching the root, counting one edge per step; that count is the leaf's level.

    Example

    B sits one edge below R, so \text{level}(B)=1. D and E each sit two edges below R, by way of A, so \text{level}(D)=\text{level}(E)=2. F also sits two edges below R, by way of C, so \text{level}(F)=2.

    Why: level counts edges, not vertices, so it directly measures the length of that particular root-to-leaf path.

  3. 3

    Take the maximum level over every leaf from Step 2.

    Example

    The levels found were 1 (for B), 2 (for D), 2 (for E), and 2 (for F). The largest is 2, so the height is 2, achieved by D, E, and F together.

    ⚡ Shortcut

    Instead of tracing every leaf by hand, compute height recursively: the height of a single-vertex tree is 0, and otherwise \text{height}(T) = 1 + \max over every child c of \text{height}(subtree rooted at c). Here, the subtree rooted at A has height 1 (since D and E sit one edge below A within that smaller tree), so \text{height}(R) = 1 + \max(\text{height}(A), \text{height}(B), \text{height}(C)) = 1 + \max(1,0,1) = 2, matching the direct count exactly. This is the version a recursive computer program actually runs.

    Why: height is defined as the largest level anywhere in the tree, and no non-leaf vertex can ever beat every one of its own descendants.

Common mistakes

  • Counting the number of vertices on the longest path instead of the number of edges, which is off by one.
  • Assuming a vertex with no children automatically sits at the shallowest level, when it might actually be the deepest one in the whole tree.
  • Forgetting that the root itself sits at level 0, not level 1.
  • Confusing "ancestor" (anyone on the path back to the root, at any distance) with "parent" (only the one adjacent vertex) while tracing a leaf upward.