← Create New Paste

Diameter of a Binary Tree: One DFS, Two Return Values, and the Off-by-One Trap

3 views
"Find the diameter of a binary tree" is a short coding interview question that tests whether you can compute two different things in one traversal. The diameter is the length of the longest path between any two nodes, measured in edges, and that path does not have to pass through the root. Why the naive approach is slow A first idea is: for every node, compute the height of its left and right subtrees and add them. If height is recomputed from scratch for each node, the total work becomes O(n^2) on a skewed tree. Mention this, then improve it. The single-pass idea Do a post-order DFS that returns the height of each subtree (the number of edges on the longest downward path, or nodes, as long as you are consistent). While you are at a node, you already know the left and right heights, so the longest path that "bends" at this node is left_height + right_height. Track the maximum of that value in an outer variable. def diameter_of_binary_tree(root): best = 0 def height(node): nonlocal best if not node: return 0 l = height(node.left) r = height(node.right) best = max(best, l + r) return 1 + max(l, r) height(root) return best Here height returns the number of nodes on the longest downward path, and l + r is exactly the number of edges on the path through the current node. That is the off-by-one trap: if you define height in edges, return -1 for an empty node instead and the bend becomes l + r + 2. Pick one definition and say it out loud. Walk through an example For the tree 1 -> (2 -> (4, 5), 3), node 4 and 5 return 1, node 2 returns 2 and records 1 + 1 = 2, node 3 returns 1, and the root records 2 + 1 = 3. The answer is 3 edges: 4-2-1-3. Complexity O(n) time, since each node is visited once, and O(h) space for the recursion stack, which is O(n) for a skewed tree. If the interviewer worries about deep recursion, offer an iterative post-order traversal with an explicit stack and a dictionary of computed heights. Follow-ups worth preparing 1. Return the path itself, not just its length: store, for each node, which child gave the max height, and reconstruct from the best bending node. 2. Diameter of an N-ary tree: keep the two largest child heights at each node. 3. Diameter of a general tree given as edges: run BFS from any node to find the farthest node, then BFS again from it. 4. Binary tree maximum path sum: the same "bend at this node" pattern, but with values and negative numbers clipped to zero. How to talk through it State the definition (edges), the naive O(n^2) idea, then the insight that height and diameter can be computed together. Interviewers mostly listen for that pattern, because it reappears in many tree problems. When a tree question turns into an unexpected follow-up during a live round, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, so you can keep explaining clearly instead of losing your train of thought.
Created Nov 17, 2026 09:34 Expires Nov 17, 2027 09:34