Quiz Entry - updated: 2026.09.29
How do depth and height differ, and how are they related?
Depth is measured from the root down to a node (a property of the node's position); height is measured from a node down to its deepest leaf (a property of the subtree below it). The height of the whole tree equals the maximum depth of any node.
| Depth of $v$ | Height of $v$ | |
|---|---|---|
| Measures | edges from the root down to $v$ | edges from $v$ down to its deepest leaf |
| Is 0 for | the root | every leaf |
| Recursion goes | up, via the parent | down, via the children |
| Recursive rule | $1 + \text{depth}(\text{parent})$ | $1 + \max(\text{height of children})$ |
| Cost for one node | $O(d_v + 1)$ | $O(\text{size of the subtree})$ |
The two meet at the extremes: the deepest leaf's depth is the same number as the root's height. That is why "the height of a tree" and "the depth of its deepest node" are interchangeable.
Tip: think of a building. Depth is how many floors you are below the roof (the root is at the top), height is how many floors are below you.