parikshan

diameter-of-binary-tree

Difficulty: Easy  ·  Topic: Trees  ·  Practice it on parikshan: /practice/diameter-of-binary-tree/start

The story

A social platform models conversations as reply trees. Each post is a node; each reply is a child. The product team wants to surface "the longest back-and-forth in this thread" because long exchanges correlate with engaged users, and engaged users are what advertisers pay for. The path does not have to start at the original post or end at a leaf; it might run from one deep reply, up through a couple of common ancestors, and back down into a different deep reply on the other side of the tree. They need the longest such path in every thread, every hour, across millions of threads.

That is diameter-of-binary-tree. Once you see this problem in this framing, you will recognise it whenever a path that may bend at any internal point is the right answer: network latency between any two hosts in a tree topology, the longest dialogue in a chatbot transcript, the worst-case path length across a routing tree.

What's actually being asked

Return the length, in edges, of the longest path between any two nodes in the tree. The path may or may not pass through the root. The empty tree and a single node both have diameter 0.

The naive approach

For each node u, compute the height of its left subtree and the height of its right subtree, sum them, and track the maximum. Naively, computing each height is an O(size of subtree) walk, and you do it for every node. On a skewed chain that is O(n²). For n = 10⁴, that is 10⁸ operations, borderline within the time limit, and trivially exceeded by a slightly larger input.

The other naive trap is collecting every pair of leaves and computing the path length between them. That is O(L²) where L is the number of leaves, and for a balanced tree with 5000 leaves it is 2.5 × 10⁷ pair operations, each one walking up the tree. Hopeless.

The key insight

Every path in a tree has a unique highest node, the lowest common ancestor of its two endpoints. So the diameter is the maximum, over all candidate top nodes u, of "the longest path that bends at u". At u, that path goes from some leaf in the left subtree, up to u, and back down to some leaf in the right subtree. Its length in edges is exactly height(left) + height(right), where height of an empty subtree is 0.

So if you knew the height of every subtree, you could compute every "bend at u" answer in O(1) and take the max. The clever bit: a single post-order traversal can return the height of each subtree while simultaneously updating a running maximum of hL + hR. One pass, two facts: the height to pass up to the parent, and the global "best diameter so far" to update on the way through.

This is the canonical "return downward, update a global" pattern, listed as recursion #2 in the Trees primer. It is also the canonical "two-fact recursion" lesson: the function returns one fact (height) and modifies another fact (the running diameter) as a side effect. Mixing the two up, returning the diameter instead of the height, is the most popular wrong solution to this problem.

Step-by-step approach

  1. Parse the level-order array into a tree of nodes.
  2. Maintain a variable best = 0 accessible to the recursion.
  3. Define height(node):
    • If node is None, return 0.
    • hL = height(node.left), hR = height(node.right).
    • Update best = max(best, hL + hR).
    • Return 1 + max(hL, hR).
  4. Call height(root). Print best.

For a 10⁴-node skewed input, use an iterative post-order: a stack of (node, processed). On a False pop, push (node, True) then both children as False. On a True pop, child heights are now known (look them up in a dict), update best, store this node's height.

Worked example

Input: [1, 2, 3, 4, 5]

       1
      / \
     2   3
    / \
   4   5

Post-order:

  • height(4) = 1, hL = hR = 0, best = max(0, 0) = 0.
  • height(5) = 1, best = 0.
  • height(2): hL = 1, hR = 1, best = max(0, 2) = 2. Returns 2.
  • height(3) = 1, hL = hR = 0, best = 2.
  • height(1): hL = 2, hR = 1, best = max(2, 3) = 3. Returns 3.

Answer: 3. The path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), three edges long.

Complexity

  • Time: O(n). One traversal, constant work per node.
  • Space: O(h) for the stack.

The naive height-per-node approach is O(n²); this is the canonical example of folding two computations (height and diameter) into a single pass to drop a factor of n.

Common pitfalls

  • Returning diameter instead of height: the recursion returns the downward depth so the parent can extend it. The diameter is a global maximum updated as a side effect. Mixing them up gives the right answer for the root's two subtrees but the wrong answer everywhere else.
  • Counting nodes instead of edges: the spec asks for edges. A single node has diameter 0, not 1. A two-node tree has diameter 1. Re-read the spec.
  • Forgetting the empty tree: [] returns 0. The recursion must short-circuit on None before any attribute access.
  • Stack overflow on a chain: a 10⁴-node skewed tree overflows Python's default recursion limit. Use the iterative post-order.

Where this shows up in the enterprise

  • Network diameter in a tree topology: AWS Route 53's geolocation routing tree, Cloudflare's Anycast prefix tree. The worst-case path between any two leaves bounds the worst-case routing latency.
  • PostgreSQL B-tree index health: PostgreSQL exposes index height, but maintenance tools internally compute the diameter of fragmented B-trees to decide when a REINDEX is worth scheduling.
  • MongoDB sharded clusters: the chunk-distribution tree is queried for the worst-case cross-shard hop count when planning a $lookup.
  • TypeScript compiler AST: long expression chains (think Promise chains or RxJS pipelines) blow up AST diameter and cause slow type checks; the compiler tracks AST depth statistics for performance regressions.
  • XGBoost and LightGBM decision trees: model interpretability tools surface the diameter of each tree as a complexity metric, the path length from the rarest input to the rarest output.
  • Game AI: chess and shogi engines compute the diameter of the searched game tree as an indicator of branching imbalance.
  • Reddit and Hacker News: surface "longest dialogue" widgets on hot threads; the underlying computation is a forest-of-trees diameter sweep.

The pattern is universal: any time the worst-case path inside a hierarchy matters, you are computing the diameter.

Variants you'll see elsewhere

  • binary-tree-maximum-path-sum: same structure, but the "two-fact" upward value is the max-gain-downward and the global is the max path sum. Identical recipe.
  • longest-univalue-path: count edges only when adjacent nodes have equal values.
  • count-good-paths: another variant where the recursion returns one fact and updates a global counter.
  • diameter-of-n-ary-tree: same idea, but at each node you combine the top two child heights.
  • tree-rerooting problems on competitive programming sites: generalisations of "compute a path-related quantity for every potential top node".

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests for instant feedback, and against per-session dynamic private tests (generated freshly per session). The dynamic tests include a right-skewed chain of 800 nodes and a balanced tree of 5000 nodes; both expose the same algorithm but only the iterative form clears both.
  2. Hints are graduated. The first hint points at the "highest node of any path" observation. The third gives you the full post-order recipe. Each costs integrity.
  3. The AI training assistant can Explain, Review, Find Bugs, Add Comments, or Optimise. In practice mode it is free; in exam mode each request docks integrity by a small amount.
  4. The dispute flow runs after the verdict. The most common dispute on diameter is candidates who returned node-count instead of edge-count and are convinced the grader is broken. The reviewer settles it.

Read the concept, attempt the problem in practice mode first, take hints only when stuck, then redo it in exam mode with no help. When you can write the post-order skeleton in under five minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write diameter from scratch. An agent will. Your job is to:

  1. Recognise that any "longest path in a tree" question decomposes by lowest common ancestor, and that one post-order pass handles all candidate top nodes at once.
  2. Tell the agent precisely: "post-order traversal, return height, update a global diameter as a side effect, use an iterative stack for skewed inputs".
  3. Read the agent's code and check that it returns the height to the parent and does not return the diameter. Confirm best (or whatever the global is called) is updated at every node, not just at the root.
  4. Stress-test on the edge cases the agent will silently miss: the empty tree, a single node, a long left-only chain, a tree where the longest path does not pass through the root.

Candidates who name "this is a diameter problem, post-order with one returned fact and one global" within five seconds are the ones who direct AI agents productively. Candidates who cannot recognise the pattern end up reading 80 lines of generated all-pairs-paths code and approving it because the small sample passes. parikshan is built to train the first kind.