In a binary tree, what is the difference between the height of a node and its depth?
answer
- one is measured downward, one upward
- which of the two can a leaf claim?
- adding a descendant changes only one of them
- root to node, versus node to deepest leaf
- the empty-subtree base case fixes the convention
basics
~20 sDepth counts edges from the root down to the node; height counts edges from the node down to its deepest descendant. Depth is fixed by where a node sits, while height depends on whatever hangs below it.
solid answer
~40 sThey measure the same kind of distance in opposite directions. A node's **depth** is the number of edges on the path from the root to it, so the root has depth 0. A node's **height** is the number of edges on the longest path from it down to a leaf, so every leaf has height 0. The height of the whole tree is the root's height, which equals the maximum depth of any node. The two are equal only at the root of a perfectly one-sided shape, never in general. Say your convention out loud: counting edges makes an empty tree height -1 and a single node height 0; counting nodes makes them 0 and 1. Either is fine, mixing them is where off-by-one bugs come from.
go deeper
Be ready to state both definitions in one breath and give the value for a leaf, for the root, and for a single-node tree. Name the counting convention before you quote any number.
Explain why the recursive height rule needs an empty-subtree base case, and how that base case silently decides whether you are counting edges or nodes for the entire codebase.
Show that depth is settled at insertion while height depends on everything below a node, and draw the consequence for any invariant or limit you enforce at write time.
Own the convention as a standard: pick edge or node counting once, encode it in names such as depth-from-root rather than a bare level, and treat two services disagreeing about it as a defect, not a style preference.
## Two measurements, opposite directions In a rooted tree there is exactly one path between the root and any node, so "distance" is unambiguous once you say which two endpoints you mean. Height and depth pick different endpoints. - **Depth of a node** = the number of edges on the path from the **root down to that node**. The root has depth 0; its children have depth 1; their children depth 2. Depth answers "how far down am I?" - **Height of a node** = the number of edges on the **longest path from that node down to a leaf** in its own subtree. Every leaf has height 0. Height answers "how deep does my subtree go?" - **Height of the tree** = the height of its root, which is the same number as the maximum depth over all nodes. A useful mental image: depth is measured with a tape hanging from the ceiling (the root), height with a tape standing on the floor (the deepest leaf under you). Both tapes are the same length only when measured on the root of a shape where every leaf sits on the deepest level. ## The two counting conventions Everything above counts **edges**. Some textbooks and interviewers count **nodes** on the path instead. The whole picture shifts by one: | | edge counting | node counting | |---|---|---| | empty tree height | -1 | 0 | | single node height | 0 | 1 | | root depth | 0 | 1 | | leaf height | 0 | 1 | Neither is more correct. What is a defect is using one convention in a bound and the other in the code that enforces it. When an interviewer asks "what is the height of a tree with one node?", the strong answer is "0 if we count edges, 1 if we count nodes — I will use edges", not a bare number. The edge convention is popular because it makes the natural recursion fall out cleanly. With `height(nil) = -1`, the rule `height(x) = 1 + max(height(left), height(right))` gives a leaf `1 + max(-1, -1) = 0`, exactly as required. Choosing `height(nil) = 0` with the same recursion silently produces node counting, which is fine as long as every bound you quote is also node-based. ## Why the distinction earns interview time **Recursion shape.** Depth is passed *down* a traversal as a parameter (`visit(child, d + 1)`); height comes *back up* as a return value. If you find yourself trying to return a depth or pass a height down, the recursion is fighting the definition. **Stability over time.** A node's depth is decided the moment it is attached: it is its parent's depth plus one, and in a tree that only grows at the leaves it never changes again. A node's height is a property of everything beneath it, so it can change every time a descendant is added — and a brand-new leaf always has height 0 no matter how deep it sits. Any rule you enforce at write time therefore wants depth, not height. Structures that need heights (balance conditions, for example) cache them per node and repair the cache along the insertion path rather than recomputing. **Complexity statements.** "This operation is O(h)" always means the height of the tree, never the depth of some particular node. The whole point of balancing is to bound that one number: keep the root's height near log2 n and every root-to-leaf walk is cheap. **Level caps.** Product rules such as "threads may nest at most five levels" are depth rules. They are checked at insertion against the parent's depth, in constant time. ## Computing them Depth of a given node is one walk from the root, or a stored counter maintained at insertion. Height of a node requires visiting its entire subtree, so computing the tree's height is O(n) time with O(h) stack space for the recursion — and that stack is real space, not free. ## The mistakes to avoid Saying a leaf's height equals its distance from the root; asserting height and depth are "the same thing from the other side" for every node (they coincide only in special shapes); quoting a height number without naming the convention; and assuming a node's height is fixed once inserted. Getting these straight costs a minute and prevents a whole family of off-by-one errors in tree code.
- What height do you assign an empty tree, and why does the choice matter?Counting edges, an empty tree has height -1, so the recursion `1 + max(height(left), height(right))` returns 0 for a leaf. Counting nodes, an empty tree is 0 and a leaf is 1. Either convention is defensible; what breaks things is quoting a bound in one convention and enforcing it in the other, which shifts every limit by exactly one.
- Which of the two can you maintain in constant time as nodes are inserted?Depth: a new node's depth is its parent's depth plus one, known at insertion and never changing while the tree only grows at the leaves. Height cannot be maintained that cheaply, because attaching a node can raise the height of every ancestor on its path; structures that need heights cache them per node and repair the cache walking back up the insertion path.
- Is the height of a tree always equal to the maximum depth of any node?Yes, as long as one convention is used for both. The longest root-to-leaf path is the same path whether you measure it from the top or the bottom, so the root's height and the deepest node's depth are the same number. It is a handy cross-check when a traversal returns a height you doubt.
Depth is your floor number counted from the roof; height is how many floors of shaft are still below you before the basement.
saying these in an interview costs you the question
- Says height and depth are the same number for every node
- Gives a leaf a height equal to its distance from the root
- Quotes a height number without naming the counting convention
- Thinks a node's height is fixed once it is inserted
- Mixes edge counting and node counting in one argument