Root Paths, Depth, and Height
A root gives each vertex in a tree a natural direction: follow parent edges toward the root, or child edges away from it. This makes it possible to describe how far a vertex lies from the root and how far its descendants extend below it. These are different measurements: depth looks upward toward the root, while height looks downward into the vertex's subtree. Together with the lowest common ancestor, they also give a convenient way to calculate the distance between any two vertices.
Throughout, a tree is a finite, connected, simple graph with no cycles. A rooted tree is a tree \(T\) with one distinguished vertex \(r\), called its root. A path has no repeated vertices, and its length is its number of edges. In a tree there is a unique path between any two vertices: connectedness gives at least one path, and two distinct paths between the same vertices would contain a cycle. This unique-path property is what makes the definitions below unambiguous.
Here, a vertex \(u\) is a descendant of \(v\) if the path from the root to \(u\) passes through \(v\). The vertex \(v\) is then an ancestor of \(u\). In particular, each vertex is both an ancestor and a descendant of itself. The subtree rooted at \(v\) consists of \(v\) and all its descendants, with the edges of \(T\) between them.
In a parent list, each nonroot vertex is assigned its parent: the next vertex on its path toward the root. The edges of the tree are exactly the parent-child pairs. Following parent assignments repeatedly reaches the root, and the number of parent edges followed is the vertex's depth. Conversely, children and their descendants determine the height below a vertex.
Computing Heights from Children
Proof. If \(v\) has no children, its only descendant is \(v\), at distance \(0\), so the maximum distance to a descendant is \(0\). Now suppose \(v\) has at least one child. Every descendant \(x\ne v\) lies below exactly one child \(u\) of \(v\): the path from \(v\) to \(x\) starts with the edge \(vu\). Its distance from \(v\) is \(1+d(u,x)\), where \(d(u,x)\) is the length of the path from \(u\) to \(x\). Among the descendants below \(u\), the largest value of \(d(u,x)\) is \(h(u)\). Therefore the largest distance from \(v\) to a descendant is \(1+\max h(u)\), with the maximum taken over its children. Finally, the subtree rooted at \(r\) is the whole tree, so its height is \(h(r)\). \(\square\)
Depth can be calculated from the parent list, while height can be calculated from the leaves upward. These calculations proceed in opposite directions: depth is accumulated from the root, and a vertex's height is determined after the heights of its children are known.
Worked Example: Depths and Heights from a Parent List
Let \(T\) have vertex set \(V(T)=\{r,a,b,c,d,e,f,g\}\), root \(r\), and edge set \(E(T)=\{ra,rb,ac,ad,be,ef,eg\}\). Equivalently, the parent list is \(p(a)=r\), \(p(b)=r\), \(p(c)=a\), \(p(d)=a\), \(p(e)=b\), \(p(f)=e\), and \(p(g)=e\). The root has no parent.
Count parent edges from \(r\). The root has depth \(0\). Vertices \(a\) and \(b\) each have one parent edge to the root, so their depths are \(1\). Vertices \(c,d,e\) each have two parent edges to the root, so their depths are \(2\). Vertices \(f,g\) each have three parent edges to the root, so their depths are \(3\). Thus \(\operatorname{depth}(r)=0\), \(\operatorname{depth}(a)=\operatorname{depth}(b)=1\), \(\operatorname{depth}(c)=\operatorname{depth}(d)=\operatorname{depth}(e)=2\), and \(\operatorname{depth}(f)=\operatorname{depth}(g)=3\).
For heights, \(c,d,f,g\) have no children, so each has height \(0\). Vertex \(a\) has children \(c,d\), both of height \(0\), giving \(h(a)=1+\max(0,0)=1\). Vertex \(e\) has children \(f,g\), both of height \(0\), giving \(h(e)=1+\max(0,0)=1\). Vertex \(b\) has the single child \(e\), giving \(h(b)=1+h(e)=2\). Finally, \(r\) has children \(a,b\), so \(h(r)=1+\max(1,2)=3\). The rooted tree has height \(3\).
Check: The longest root-to-vertex paths have three edges: \(r,b,e,f\) and \(r,b,e,g\). This agrees with \(h(r)=3\). From \(b\), the longest downward paths are \(b,e,f\) and \(b,e,g\), each of length \(2\), agreeing with \(h(b)=2\).
Pairwise Distance and the Lowest Common Ancestor
The root paths of two vertices share an initial segment starting at the root. They cannot separate and later meet again: that would give two different paths between the point where they separated and the point where they met, contradicting uniqueness of paths in a tree. Their last shared vertex is called their lowest common ancestor.
Proof. The root paths from \(r\) to \(x\) and from \(r\) to \(y\) share exactly the path from \(r\) to \(w\). Its length is \(\operatorname{depth}(w)\). After \(w\), the path to \(x\) has length \(\operatorname{depth}(x)-\operatorname{depth}(w)\), and the path to \(y\) has length \(\operatorname{depth}(y)-\operatorname{depth}(w)\). Joining these two portions at \(w\) gives a path from \(x\) to \(y\). The portions have no other vertex in common, because any further common vertex would be a common ancestor deeper than \(w\). Thus this joined path is the unique \(x\)-\(y\) path, and its length is \((\operatorname{depth}(x)-\operatorname{depth}(w))+(\operatorname{depth}(y)-\operatorname{depth}(w))\), which equals the stated formula. This argument also covers \(x=y\): then \(w=x=y\) and the formula gives distance \(0\). \(\square\)
Worked Example: Distances Using a Lowest Common Ancestor
Use the tree from the previous example, with \(V(T)=\{r,a,b,c,d,e,f,g\}\) and \(E(T)=\{ra,rb,ac,ad,be,ef,eg\}\). Find \(d(c,f)\), \(d(c,d)\), and \(d(b,g)\).
The root paths to \(c\) and \(f\) are \(r,a,c\) and \(r,b,e,f\). Their only common vertex is \(r\), so \(\operatorname{LCA}(c,f)=r\). Their depths are \(2\) and \(3\), and the root has depth \(0\). Hence \(d(c,f)=2+3-2(0)=5\). Directly, the unique path is \(c,a,r,b,e,f\), which has five edges.
The root paths to \(c\) and \(d\) are \(r,a,c\) and \(r,a,d\), so their lowest common ancestor is \(a\), of depth \(1\). Both vertices have depth \(2\), giving \(d(c,d)=2+2-2(1)=2\). The path \(c,a,d\) has two edges.
The root paths to \(b\) and \(g\) are \(r,b\) and \(r,b,e,g\), so \(\operatorname{LCA}(b,g)=b\), of depth \(1\). Their depths are \(1\) and \(3\), giving \(d(b,g)=1+3-2(1)=2\). The path \(b,e,g\) has two edges.
Check: Each formula value matches the number of edges in the explicitly traced unique path: \(5\), \(2\), and \(2\), respectively.
Worked Example: A Different Branching Pattern
Let \(T\) have vertex set \(V(T)=\{o,p,q,s,t,u,v,w\}\), root \(o\), and edge set \(E(T)=\{op,oq,ps,qt,qu,tv,vw\}\). Its parent list is \(p(p)=o\), \(p(q)=o\), \(p(s)=p\), \(p(t)=q\), \(p(u)=q\), \(p(v)=t\), and \(p(w)=v\).
Counting parent edges gives depth \(0\) for \(o\), depth \(1\) for \(p,q\), depth \(2\) for \(s,t,u\), depth \(3\) for \(v\), and depth \(4\) for \(w\). The leaves \(s,u,w\) have height \(0\). Since \(v\)'s only child is \(w\), \(h(v)=1+0=1\). Since \(t\)'s only child is \(v\), \(h(t)=1+1=2\). Vertex \(p\) has only child \(s\), so \(h(p)=1+0=1\). Vertex \(q\) has children \(t,u\), so \(h(q)=1+\max(2,0)=3\). Finally, \(h(o)=1+\max(1,3)=4\).
To find \(d(v,u)\), compare their root paths: \(o,q,t,v\) and \(o,q,u\). Their lowest common ancestor is \(q\), of depth \(1\). Since \(\operatorname{depth}(v)=3\) and \(\operatorname{depth}(u)=2\), \(d(v,u)=3+2-2(1)=3\). The path \(v,t,q,u\) has three edges.
Check: The longest path from the root is \(o,q,t,v,w\), with four edges, agreeing with \(h(o)=4\). The traced \(v\)-to-\(u\) path also confirms the distance calculation independently.
Common Pitfall: Adding Depths Without Removing the Shared Part
A frequent error is to add the two depths and treat the result as the distance between the vertices. That counts the shared portion of the root paths twice. In the first example, \(f\) and \(g\) each have depth \(3\), so the incorrect calculation \(d(f,g)=3+3=6\) counts the path from \(r\) to their common ancestor \(e\) twice. Their lowest common ancestor is \(e\), with depth \(2\), so the correct calculation is \(d(f,g)=3+3-2(2)=2\). The path \(f,e,g\) has exactly two edges.
Depth and height are also easy to confuse. In the first example, \(b\) has depth \(1\) because it is one edge from the root, but height \(2\) because its farthest descendants are two edges below it. Depth measures position relative to the root; height measures the downward reach of a subtree. A one-vertex rooted tree is consistent with both definitions: its root has depth \(0\), has no children, and has height \(0\).
Why These Quantities Are Useful
Depths provide a compact record of where vertices lie relative to a chosen root. Heights summarize how far a subtree extends below its root vertex, and the recurrence lets us calculate them from the leaves upward. Pairwise distances can be found from depths once the lowest common ancestor is identified; there is no need to trace the full path every time. The path remains a valuable check, especially when vertices lie in separate branches and their root paths share several edges.
For any distance calculation, first identify the common initial part of the two root paths. Its last vertex is the lowest common ancestor. Subtracting twice its depth removes the shared edges counted in both root-to-vertex lengths. If one vertex is an ancestor of the other, the lowest common ancestor is the ancestor itself, and the formula reduces to the difference of their depths.
Check Your Understanding
Use parent lists and root paths to justify each answer.
- In the tree with root \(r\) and edges \(ra,rb,ac,ad,be\), find the depth of every vertex and the height of every vertex.
- In a rooted tree, \(x\) and \(y\) have depths \(5\) and \(4\), and their lowest common ancestor has depth \(2\). Calculate \(d(x,y)\), then state what part of the root paths the subtraction removes.
- Prove that if \(x\) is an ancestor of \(y\), then \(d(x,y)=\operatorname{depth}(y)-\operatorname{depth}(x)\).
- A vertex has three children whose subtree heights are \(0,2,4\). Find its height and explain which child determines it.
- Explain why the root of a one-vertex tree has depth \(0\) and height \(0\), even though it has no children.