Diameter of a Binary Tree: when the longest path avoids the root

The diameter is the longest path between any two nodes, measured in edges. That path might cross the root — or it might live entirely in a subtree, completely ignoring the root's existence. That "may or may not pass through the root" note in the problem statement is not flavor text; it is the central design challenge.

In this tree, the longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), which is 3 edges. It does cross the root. But consider a tree where the deep subtree hangs entirely off the left child — the root is just a bystander.

The key insight: at any node, the diameter passing through that node equals the depth of its left subtree plus the depth of its right subtree. The global diameter is the maximum of that value across all nodes. Everything follows from this.

The problem

Given the root of a binary tree, return the length of the diameter — the longest edge-path between any two nodes. The path may or may not pass through the root; the length is the number of edges, not nodes. Full statement: LeetCode 543.

Constraints:
- The number of nodes in the tree is in the range [1, 10^4].
- -100 <= Node.val <= 100

What the constraints force

The problem guarantees [1, 10^4] nodes and values in [-100, 100]. The value range does not matter at all — the algorithm only cares about structure, never values. The node count does matter.

10^4 nodes is large enough that an O(n^2) solution will feel it — calling a depth function for each node means up to 10^8 operations in the worst case (a fully skewed chain). That is borderline in practice and would likely TLE on a strict judge. The constraint is silently nudging you toward a linear pass.

The lower bound of 1 node is worth noting: the minimum possible answer is 0 (a single node has no edges), and the code must return 0 gracefully without special-casing.

Recursion depth: in the worst case (a fully left-skewed chain of 10^4 nodes), your DFS call stack is 10^4 deep. Python's default recursion limit is 1000, so a naive recursive solution will hit RecursionError on pathological inputs. For contest/interview purposes this is usually ignored, but it is worth being aware of. C# has a much larger default stack and does not have this concern.

Approach 1: Brute force — recompute depth at every node

The straightforward reading: iterate over every node, compute how deep the left and right subtrees are at that node, add them together, keep the max. Two passes per node — one to traverse all nodes, one to compute depth from each.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
 
        max_diameter = 0
 
        def get_depth(node: TreeNode) -> int:
            if not node:
                return 0
            return 1 + max(get_depth(node.left), get_depth(node.right))
 
        def traverse(node: TreeNode) -> None:
            nonlocal max_diameter
            if not node:
                return
            left_depth = get_depth(node.left)
            right_depth = get_depth(node.right)
            max_diameter = max(max_diameter, left_depth + right_depth)
            traverse(node.left)
            traverse(node.right)
 
        traverse(root)
        return max_diameter

public class Solution {
    private int maxDiameter = 0;
 
    public int DiameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        maxDiameter = 0;
        Traverse(root);
        return maxDiameter;
    }
 
    private int GetDepth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.Max(GetDepth(node.left), GetDepth(node.right));
    }
 
    private void Traverse(TreeNode node) {
        if (node == null) return;
        int leftDepth = GetDepth(node.left);
        int rightDepth = GetDepth(node.right);
        maxDiameter = Math.Max(maxDiameter, leftDepth + rightDepth);
        Traverse(node.left);
        Traverse(node.right);
    }
}

This works, but it recomputes the depth of every descendant for every ancestor. Node 4 in the example above gets its depth computed when you call get_depth from node 2, again when called from node 1. For a balanced tree that is O(n log n); for a skewed chain it hits O(n^2).

Time: O(n^2). Each of the n nodes triggers a full depth traversal of its subtree.

Space: O(n) for the call stack — two simultaneous recursive calls, both up to O(h) deep, where h is tree height.

Approach 2: Optimized DFS — depth and diameter in one pass

The waste in the brute force is obvious once you see it: get_depth rewalks subtrees that have already been walked. The fix is equally obvious — have each DFS call return its own depth, so the parent never needs to recompute it.

This is a post-order traversal. You process children first, collect their depths, then compute the diameter at the current node using the already-known depths. No redundant work.

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.max_diameter = 0
 
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)
            # diameter through this node = left arm + right arm
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            # return depth to parent — they add 1 for the edge to this node
            return 1 + max(left_depth, right_depth)
 
        dfs(root)
        return self.max_diameter

public class Solution {
    private int maxDiameter = 0;
 
    public int DiameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        DFS(root);
        return maxDiameter;
    }
 
    private int DFS(TreeNode node) {
        if (node == null) return 0;
        int leftDepth = DFS(node.left);
        int rightDepth = DFS(node.right);
        maxDiameter = Math.Max(maxDiameter, leftDepth + rightDepth);
        return 1 + Math.Max(leftDepth, rightDepth);
    }
}

Time: O(n). Each node is visited exactly once. At each visit the work is O(1) — two recursive calls (already paid for), one max, one addition, one comparison.

Space: O(h) where h is tree height. Balanced tree: O(log n). Skewed chain: O(n). The call stack depth is bounded by h, and the diameter variable lives on the heap (Python self, C# field).

Hand trace through root = [1, 2, 3, 4, 5]

Walk the DFS post-order — children before parents:

dfs(4):  left=dfs(null)=0, right=dfs(null)=0
         diameter candidate: 0+0=0
         return 1+max(0,0) = 1

dfs(5):  left=dfs(null)=0, right=dfs(null)=0
         diameter candidate: 0+0=0
         return 1+max(0,0) = 1

dfs(2):  left=1 (from node 4), right=1 (from node 5)
         diameter candidate: 1+1=2  -> max_diameter = 2
         return 1+max(1,1) = 2

dfs(3):  left=dfs(null)=0, right=dfs(null)=0
         diameter candidate: 0+0=0
         return 1+max(0,0) = 1

dfs(1):  left=2 (from node 2), right=1 (from node 3)
         diameter candidate: 2+1=3  -> max_diameter = 3
         return 1+max(2,1) = 3

Final: max_diameter = 3

The max is set twice: first 2 at node 2 (the path 4->2->5), then 3 at node 1 (the path 4->2->1->3). The global variable accumulates the best seen so far — there is no going back up to "fix" an earlier value.

Edge cases that matter

Single node (root = [1]): dfs(1) calls dfs(null) twice, both return 0. Diameter candidate is 0+0=0. Returns 1. max_diameter = 0. Correct — no edges exist.

Two nodes (root = [1, 2]): dfs(2) returns 1. dfs(null) returns 0. At node 1, candidate is 1+0=1. max_diameter = 1. One edge, one diameter. Correct.

Linear chain (e.g., 1->2->3->4): every node has one child, never two. The diameter is never updated beyond the number of nodes on the path from root to leaf — which is n-1 edges. At each node, left_depth + right_depth is either k + 0 = k or 0 + 0 = 0 depending on which direction the chain goes. The answer is n-1. Correct.

Diameter in a subtree, not through root: imagine a very deep left subtree with two long branches at the bottom, and a trivial right subtree at the root. The maximum left_depth + right_depth occurs at the branching node deep in the left subtree, not at the root. The global variable captures it because we update max_diameter at every node, not just at the root.

Null root: the problem guarantees at least 1 node, so root = null is technically out of bounds. But both implementations return 0 safely if passed null anyway — dfs(null) immediately returns 0, max_diameter stays 0.

The pattern: post-order accumulation with a side-channel result

This problem is the clearest example of a pattern that appears throughout tree problems: you want to compute something at every node that depends on children's results, but you also want to accumulate a global best as you go. The recursive function serves two purposes simultaneously — it returns the local metric (depth, here) upward to the parent, and it updates the global accumulator (max_diameter) as a side effect.

The local return value and the global accumulator track different things. Depth is "how long is the path from me down to my deepest leaf." Diameter is "what is the longest path through me." The function returns depth; it updates diameter. Both happen in one pass.

This dual-purpose post-order DFS shows up in:

• Binary Tree Maximum Path Sum (124): return the best single-arm gain upward; update the global best path sum (which can span both arms) as a side effect. The structure is nearly identical to 543 — replace "depth" with "max gain" and "edge count" with "sum."
• Longest Univalue Path (687): return the longest arm with a consistent value; update the global longest path as a side effect. Same skeleton, different local predicate.
• Balanced Binary Tree (110): return height upward; update a "is balanced" flag as a side effect. The accumulator turns boolean instead of integer.

Once you see the shape — return local metric up, accumulate global best sideways — you recognize it instantly.

Brute force vs. optimal: when does the gap actually matter?

For small trees the O(n^2) vs. O(n) difference is academic. For n = 10^4 with a pathological shape (a chain), brute force hits roughly 5 * 10^7 operations — sluggish but possibly within a generous time limit. The optimal DFS does 10^4.

What I would actually ship: the optimized DFS, without hesitation. The code is not harder to understand than the brute force — in fact I find it cleaner, because the "compute depth, update diameter" logic lives in one place rather than split across two separate recursive functions. The brute force's only advantage is that the two concerns (traversal and depth) are visually separated, which can help when you are first reasoning about the problem. Once you have convinced yourself it is correct, collapsing the two into one pass is a straightforward refactor.

Comparison table

Where this sits in the trees series

This is problem nine in the series. The earlier problems built up the vocabulary: Maximum Depth (104) taught the depth-computation pattern that brute-force 543 reuses directly. Invert Binary Tree (226) and Same Tree (100) showed that post-order DFS is the natural way to combine child results at a parent. Subtree of Another Tree (572) and Validate BST (98) added side-channel flags into the DFS return.

543 is the first problem in this series where the answer is not directly returned from the DFS — it is accumulated globally while the DFS returns a different quantity (depth). That split is the conceptual step this problem is teaching.

Binary Tree Maximum Path Sum (124) is the hardest direct neighbor: the same post-order accumulation pattern, but depth becomes "gain from a subtree arm" and you must handle negative values correctly (you can choose to exclude an arm if its contribution is negative). The shape of the solution is nearly identical; the difficulty comes from reasoning about negative gains.

Longest Univalue Path (687) adds a value constraint: the path must consist of nodes with the same value. The post-order accumulation remains, but the arm length resets to 0 when the value changes.

Count Good Nodes in Binary Tree (1448) is a different flavor: you pass a maximum value downward (pre-order) rather than accumulating upward (post-order). It is a good counterexample to study after 543, because the direction of information flow flips.

Diameter of N-ary Tree (1522) generalizes directly: instead of left and right children, each node has an arbitrary list of children. You take the two longest arms and sum them. The same dual-purpose DFS, generalized.