Why can a tree's longest node-to-node path avoid the root entirely, and how does one traversal still find it?
answer
- every path has one topmost node
- the root is one candidate out of n
- a deep two-branched subtree beats a lopsided top
- record both branches, return only one
- the stack is the space cost
basics
~20 sA tree's longest path has one highest node, and nothing forces that to be the root — a deep two-branched subtree beats a lopsided top. One post-order pass tracks the largest combined branch height over all nodes.
solid answer
~40 sEvery path has one topmost node, and the path is that node's deepest reach on the left joined to its deepest reach on the right. The root is just one candidate among `n`: a root with one shallow child and one deep, bushy child keeps its longest path entirely inside the bushy side. So a single post-order pass scores every node. Define `height(x)` as the edges on the longest downward path from `x`, with `height(null) = -1`. At each node the candidate is `height(left) + height(right) + 2`, recorded into a running maximum, while the value returned upward is `1 + max(height(left), height(right))` — one branch only, since a path continuing to the parent can use just one side. Time `O(n)`, space `O(h)` for the stack.
go deeper
Be able to draw a tree whose longest path misses the root and point at it. Knowing that the answer is a maximum over all nodes, not a property of the root, is the bar here.
Explain the record-both-return-one asymmetry and why a path continuing to the parent may use only one branch. Give time and space, and pick an edge or node convention explicitly.
Show you would catch a colleague's version that recomputes heights, and reason about stack depth on production-shaped skewed trees before calling the single pass safe.
Treat it as a measurement question: the diameter bounds worst-case traversal cost in a tree-shaped system, so decide how often it must be recomputed and whether an incremental estimate is enough versus a full pass on every change.
## The claim to dismantle Asked for the longest node-to-node path in a tree — its **diameter** — many candidates answer "go down the left, go down the right, add them". That computes only the longest path *through the root*, which is a lower bound on the diameter and often strictly smaller. A related wrong answer, "it's twice the height", is an upper bound that is only reached when two deepest leaves happen to sit under different children of the root. Both errors come from the same place: forgetting that a path has a topmost node and that this node is chosen by the data, not by you. ## Setting A campus network is cabled as a tree: one uplink per device, no loops. You want the longest cable run between any two devices, because that run bounds the worst-case propagation delay and tells you which pair to test first. The distribution switch at the top of the diagram is the root only because of how the diagram was drawn — the longest run may live entirely inside one wing of the building. ## Why the top node of a path can be anything Pick any path between two nodes `u` and `v` in a tree. Walk from `u` toward `v`; the depth strictly decreases for a while, reaches a minimum at exactly one node, then strictly increases. That unique shallowest node on the path is the pair's lowest common ancestor, and the path is (`u` up to it) + (it down to `v`). So the set of all paths is partitioned by their topmost node, and the diameter is the maximum over all `n` choices of that node. That immediately gives the shape of the algorithm and the counterexample. Take a root with a right child that is a single leaf, and a left child that heads a deep balanced subtree with two long chains hanging off it. The longest path joins the ends of those two chains, meeting at the left child. Any path through the root must spend one of its two halves on the single-leaf side, wasting the budget. The root loses. ## The one-pass computation Fix a convention and say it out loud, because half of all off-by-one arguments in this problem are two people using different ones. Measuring in **edges**: - `height(null) = -1` - `height(x) = 1 + max(height(x.left), height(x.right))` Then for a node `v`, the longest path whose topmost node is `v` has `height(v.left) + height(v.right) + 2` edges: the two `+1`s are the edges from `v` down into each child. For a leaf this gives `-1 + -1 + 2 = 0`, correctly saying a single node is a zero-edge path. The post-order pass does two things at each node, and separating them is the whole insight: - **Record** `height(left) + height(right) + 2` into a running maximum. This is the answer *if* the best path tops out here. - **Return** `1 + max(height(left), height(right))` to the parent. Only one branch, because a path that continues upward through `v` enters `v` from above and can descend into just one of its children. A candidate who returns the two-branch sum upward has built something that is not a height and produces nonsense one level up. The asymmetry — record both, return one — is the reusable idea, and it is the same skeleton behind other "best path anchored at a node" tree computations. Cost: each node is visited once and does constant work, so `O(n)` time. Space is the recursion stack, `O(h)`: `O(log n)` on a balanced tree, `O(n)` on a chain. Stack depth is part of space complexity, and on a deep skewed tree it is the part that actually breaks. ## Sanity checks worth memorizing - **A chain of `n` nodes.** Diameter `n - 1` edges, and the topmost node of that path is the chain's own root — a case where the root does win, which is why one example is never enough to establish the general claim. - **A single node.** Zero edges. If your convention says one, you are counting nodes, which is fine as long as you say so; node count is edge count plus one. - **A perfect tree of height `h`.** Diameter `2h`, the upper bound, reached exactly because two deepest leaves sit under different root children. ## The alternative you should know exists On an unrooted or arbitrarily-rooted tree, there is a two-pass trick: from any node, find the farthest node `x`; from `x`, find the farthest node `y`; the distance from `x` to `y` is the diameter. It is two traversals instead of one, `O(n)` either way, and it needs no notion of root at all. It is worth naming because it shows the diameter is a property of the tree, not of the root you happened to hang it from — which is the point the "through the root" answer misses.
- Where do you keep the diameter candidate if the recursion returns only a height?Outside the recursion, as a running maximum updated at every node — either an accumulator threaded through the calls or a pair returned upward. The point is that the recorded value (both branches joined) and the returned value (one branch) are different quantities; conflating them is the standard bug.
- Is the longest path through the root an upper or a lower bound on the diameter?A lower bound: it is one of the `n` candidates the maximum is taken over, so it can only be smaller or equal. Twice the tree's height is the other side — an upper bound, attained only when two deepest leaves sit under different children of the root. Quoting either one as the answer is wrong in a predictable direction.
- How does the result change if the path is measured in nodes rather than edges?Every value shifts by one: a node count equals the edge count plus one, and the empty-subtree base case becomes 0 instead of -1. Neither convention is more correct; state which one you are using before you argue about a boundary, because almost every disagreement here is two conventions colliding.
The longest corridor in a branching building need not pass through the lobby; it may run wall to wall inside one wing.
saying these in an interview costs you the question
- Says the longest path always passes through the root
- Computes the diameter as exactly twice the tree height
- Returns the two-branch sum upward instead of one branch
- States O(1) space, ignoring the recursion stack
- Mixes node counts and edge counts inside one argument