Diameter of Binary Tree — The Zipline Route

Boss 3: The Zipline Route

Boss 2's template had one channel: each node reports one number upward. This boss introduces the move that separates tree tourists from tree residents: the answer you report upward and the answer you're hunting are different numbers.

Master this split and Boss 14, a certified Hard and this dungeon's summit, becomes a reskin.

The story

The adventure park's treehouse complex, platforms connected by rope bridges:

          Platform 1
         /          \
    Platform 2    Platform 3
     /      \
Platform 4  Platform 5

Marketing wants to install one glorious zipline: the longest possible cable between any two platforms, measured in bridges (edges). The cable may pass through platforms, and critically, it may bend at a platform: come up from one branch and head down the other.

Look at the map. The longest route is Platform 4 → 2 → 5? Three platforms, 2 bridges. Or 4 → 2 → 1 → 3: 3 bridges. That one bends at Platform 1, rising from the deep left side and dropping to the right.

Now stretch your imagination to a complex where Platform 3's side is a stub but Platform 2's side is a fifty-platform jungle. The longest cable might run entirely inside the left jungle, bending at some interior platform, never visiting Platform 1 at all. That's the trap of this problem: the best answer can live anywhere, not just at the root.

The problem, dressed up properly

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

LeetCode 543. Note: edges, not nodes. Boss 2's counting-convention warning, now live ammunition.

The naive attempt

The longest path bending at node X is depth(X.left) + depth(X.right). So: for every node, compute both depths, take the best.

def diameter_of_binary_tree(root):
    def depth(node):
        if not node:
            return 0
        return 1 + max(depth(node.left), depth(node.right))
 
    best = 0
    def walk(node):
        nonlocal best
        if not node:
            return
        best = max(best, depth(node.left) + depth(node.right))
        walk(node.left)
        walk(node.right)
    walk(root)
    return best

Correct! And O(n²) in the worst case: walk visits n nodes, and each visit launches a full depth survey of everything below. On a vine-shaped tree, that's the arithmetic-series death: n + (n-1) + (n-2) + ... The park's surveyors re-measure the same branches thousands of times.

The waste is painfully specific: depth at a node already computes the depths of everything below it, then throws them away, and walk asks again.

The weapon: report depth up, log the bend on the side

One traversal. Each platform does Boss 2's job, report 1 + max(left, right) upward, and one extra thing while it has both children's reports in hand: it checks the cable that would bend through itself, left + right bridges, and logs it into a shared best-so-far.

Two channels:

• Return value (the upward report): my depth, information my parent needs.
• Side channel (the log): the best bend seen anywhere, information the problem wants.

Why can't the bend itself be reported upward? Because a bent path is used up: once the cable turns at a platform, it can't also continue up to the parent, a zipline has two ends, not three. The parent can only extend a straight arm, hence it receives the depth. The bend is a completed candidate, so it goes to the judge, not to the parent. That's the entire philosophy: report what's extendable, log what's complete.

Watching it work

depth(4) → left 0, right 0 → log 0+0=0 → report 1
depth(5) → log 0 → report 1
depth(2) → left 1, right 1 → log 1+1=2 → report 2
depth(3) → log 0 → report 1
depth(1) → left 2, right 1 → log 2+1=3 → report 3 (nobody's listening)

best logged: 3 ✓   (the 4 → 2 → 1 → 3 route)

One visit per platform. The n² became n by not forgetting: every depth is computed once, used twice (once by the parent, once by the local bend check), and never recomputed.

The code

def diameter_of_binary_tree(root: TreeNode | None) -> int:
    best = 0
 
    def depth(node):
        nonlocal best
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        best = max(best, left + right)      # complete candidate: log it
        return 1 + max(left, right)         # extendable arm: report it
 
    depth(root)
    return best

Gotchas

1. Returning left + right + 1 upward. The three-ended zipline. The parent extends your arm, not your bend. Report 1 + max(left, right). Mixing the two channels is the bug in this problem family.

2. Edges vs nodes, again. This problem counts edges, so a leaf's bend check is 0+0 and a single-node tree has diameter 0. If the expected answer is consistently one less than yours, you're counting platforms instead of bridges.

3. Initializing best inside the recursion. best must live outside depth (a nonlocal, a class field, or a one-element list). Re-declaring it per call resets the log and returns whatever the root's bend happened to be.

4. Assuming the answer passes through the root. depth(root.left) + depth(root.right) alone is exactly the naive trap this problem was designed to punish. The log exists because the best bend can hide anywhere. Test on a tree with one deep, bushy arm.

Complexity

One post-order pass, constant work per node.

Time: O(n). Space: O(h) for the stack.

Boss down. XP gained.

The zipline runs 4 → 2 → 1 → 3, marketing photographs a terrified-but-thrilled first rider, and the surveyor who computed it never re-measured a single branch.

What you walked away with:

• Two channels: return the extendable arm upward, log the completed candidate sideways
• Bends are complete (two ends used), arms are extendable, never report a bend as an arm
• The O(n²) → O(n) move: compute child answers once, use them for both jobs
• This shape is a master key; Boss 14 will open with it

So far every boss processed one tree. Time to hold two at once.

Next up: Boss 4 — The Mobile Maker. An artist hangs balanced mobile sculptures, and a mobile is only sellable if, at every joint, the two hanging sides differ in height by at most one. Same two-channel trick, but the side channel carries a verdict instead of a length, and one clever encoding makes the whole check a single pass.