543. Diameter of Binary Tree - Detailed Explanation

Brute Force – Java Implementation:

Complexity Analysis (Brute Force): In the worst case, for every node we compute the height of its subtrees by traversing those subtrees. If the tree has n nodes, computing height is O(n) in the worst case, and doing that for every node leads to O(n²) time complexity. For a balanced tree, it will be better (closer to O(n log n)), but worst-case (skewed tree) is quadratic. Space complexity is O(n) due to recursion depth (in worst case, the tree height is n). We also use additional stack frames for each recursive call. No extra data structures are used aside from recursion.

Optimal Recursive Approach (DFS)

Idea: We can optimize the above approach by computing the height of subtrees and the diameter in a single DFS traversal. The key observation is that when we compute the height of each subtree, we can simultaneously update a global maximum for the diameter. Using a DFS (Depth-First Search) post-order traversal, we can get the heights of left and right subtrees of a node, then calculate the path length through that node, and update the diameter if this path is longer than the current maximum. This way, each node is visited only once. This approach is often implemented with recursion: the recursive function returns the height of the current node, but also updates a global (or outer scope) variable tracking the best diameter found so far.

How it works: For each node, when the recursive DFS returns, we have:

• leftHeight = max depth of its left subtree (number of nodes from the node down to the deepest leaf on the left side).

• rightHeight = max depth of its right subtree.
  We compute leftHeight + rightHeight which effectively gives the number of nodes on the longest path through this node minus 1 (or equivalently, the number of edges on that path). We compare this sum to our global maximum diameter and update if larger. Then the function returns 1 + max(leftHeight, rightHeight) as the height of the node (one more than the greater of its two subtree heights). By doing this in one recursion, we avoid recalculating heights repeatedly.

This DFS approach gives us O(n) time complexity, since we visit each node exactly once and do O(1) work at each node. The space complexity is O(n) in the worst case (due to the recursion stack for a skewed tree, which is of height n). For a balanced tree, the recursion depth is O(log n). We can also consider optimizing space by converting the recursion to an explicit stack-based traversal (to avoid the function call stack), but the space order remains linear in n in the worst case either way (stack or recursion). We discuss an iterative alternative in the next section, but first, here’s the recursive DFS solution:

Optimal DFS – Python Implementation:

Time Complexity: This DFS solution runs in O(n) time, where n is the number of nodes, since each node’s height is computed once and each node is visited once. We eliminate the repeated work of recomputing subtree heights.

Space Complexity: O(n) in the worst case due to recursion (the recursion stack can go as deep as the tree’s height, which in the worst case of a skewed tree is n). In a balanced tree, the height is O(log n), so space would be O(log n). We use only a few extra variables aside from the recursion stack (the diameter variable and a few locals).

Space Optimization: If recursion is a concern (for very deep trees, Python’s recursion may hit limits around depth ~1000), we can implement the same logic using an explicit stack to avoid recursion. Another optimization in some languages is tail-call optimization, but our recursion isn’t tail-call (we use results of recursive calls to compute the return value). Generally, the recursion is simple and efficient for n up to 10,000 (as given in constraints), but in Python a highly skewed tree might exceed the default recursion depth. In practice, one might increase the recursion limit or use an iterative approach for such cases. However, conceptually the approach remains the same (post-order traversal computing heights and updating diameter).

Iterative Approach (Optional)

It is also possible to solve this problem iteratively, though it can be a bit more involved. One idea is to use a two-pass BFS/DFS method known from tree theory:

1. First BFS/DFS: Start from an arbitrary node (for a rooted binary tree, starting at the root is convenient). Perform a BFS (breadth-first search) to find the farthest node from the start. In a tree, the farthest node found will be one end-point of the diameter.

2. Second BFS/DFS: Then perform another BFS starting from that farthest node found in step 1, to find the farthest node from it. The distance (number of edges) between these two farthest nodes is the diameter.

In a general tree (not necessarily binary), this two-BFS method finds the diameter in linear time. In a binary tree, we need to be careful to treat the tree as an undirected graph (meaning from a given node we should be able to traverse to its parent as well as its children). This can be done by storing parent pointers or by performing BFS within the tree structure (which naturally only goes downward) and keeping track of depth. A simpler variant in a rooted binary tree is:

• Do a DFS to compute depths and identify the deepest leaf node.

• Then do another DFS from that deepest leaf to measure the distance to the farthest node from it.

This approach also runs in O(n) time and uses O(n) space for queues/parent pointers. However, implementing it requires additional data structures (like a map from child to parent, or modifying the tree nodes to include parent links) and two traversal passes.

Another possible iterative strategy is to simulate the DFS using a stack (post-order traversal). You would push nodes onto a stack and traverse to the leftmost leaf, then as you backtrack you compute heights. To do this, one can use a stack of pairs (node, state) to indicate whether the node has been processed after visiting children. When processing a node after its children, you would compute the height and update the global diameter. This yields the same results as the recursive DFS. The complexity remains O(n) time and O(n) space.

Since the recursive DFS solution is simpler and clear, the iterative approaches are generally not necessary unless you must avoid recursion. It’s good to know they exist: for example, in languages or environments where deep recursion is problematic, one can convert the DFS to an iterative form. But the end result and complexities are the same.

Step-by-Step Walkthrough

Let’s walk through the optimal DFS approach on an example to see how it computes the diameter. Consider the tree from Example 1:

Using the DFS approach, we perform a post-order traversal (compute children results before the parent). Here’s a step-by-step dry run:

• Start at root (node 1): We call dfs(1). This will internally call dfs(2) for the left child and dfs(3) for the right child, then use their results.

  • Visit node 2 (left child of 1): dfs(2) will call dfs(4) and dfs(5) before finishing.

    • Visit node 4 (left child of 2): dfs(4) calls dfs(4.left) which is dfs(None) and returns 0 (height of empty subtree). Similarly, dfs(4.right) returns 0. Now at node 4, left_height = 0 and right_height = 0. The path through node 4 has length 0 + 0 = 0 edges, which we compare to the current max diameter (initially 0). The max diameter remains 0. The height returned for node 4 is 1 + max(0, 0) = 1.
    • Visit node 5 (right child of 2): Similarly, dfs(5.left) and dfs(5.right) return 0 (no children). So for node 5, left_height = 0, right_height = 0, path through 5 = 0 edges. Max diameter stays 0. Height of node 5 = 1 + max(0, 0) = 1.
    • Back at node 2: Now we have results for node 2’s children. left_height = 1 (from node 4), right_height = 1 (from node 5). The longest path through node 2 uses both children: it has length 1 + 1 = 2 edges (4 → 2 → 5). We update the global diameter: it was 0, now it becomes 2 (since 2 > 0). Node 2’s height is 1 + max(1, 1) = 2 (node 2 plus the taller of its children’s heights). We return height = 2 for node 2.

  • Visit node 3 (right child of 1): dfs(3) sees that node 3 has no children. So left_height = 0, right_height = 0 for node 3, path through 3 = 0 edges. The global diameter is currently 2, and 0 is not greater, so it stays 2. Height of node 3 = 1. Return height = 1 for node 3.

  • Back at root (node 1): Now we combine results for node 1. left_height = 2 (from node 2), right_height = 1 (from node 3). The longest path through node 1 goes through both children: length 2 + 1 = 3 edges (this corresponds to the path 4 → 2 → 1 → 3). We compare 3 with the current global diameter (which was 2) and update it to 3, since 3 is larger. The height of node 1 would be 1 + max(2, 1) = 3 (the tree’s height in nodes is 4, which is height 3 in 0-indexed edges terms). The DFS traversal is complete.

• Result: The global diameter has been updated to 3, which is the length of the longest path found. This matches the expected answer. We return 3.

Throughout this process, each node was visited once, and at each node we performed a constant amount of work (a couple of additions, comparisons, and a max). The global diameter was updated whenever we found a longer path. Notice how we never recomputed the height of any subtree more than once – each subtree’s height was computed bottom-up and reused directly in computing its parent’s values.

Common Mistakes & Edge Cases

Common Pitfalls:

• Off-by-One Errors in Diameter Calculation: It’s easy to confuse the definition of diameter in terms of edges vs nodes. The problem explicitly defines diameter in terms of number of edges. If your approach computes the number of nodes on the longest path, remember to convert it to edges (which is nodes count minus 1). The DFS solution above uses left_height + right_height (where left_height and right_height are counts of nodes in each subtree) which correctly gives number of edges on the path through the node. A common mistake is to add 1 mistakenly, which would yield the number of nodes instead of edges. Make sure to clarify the definition: e.g., a tree with a single node should have diameter 0, not 1.

• Considering Only Root’s Children: Some might initially think the diameter is just left_depth + right_depth of the root. That’s only the path through the root. The longest path could lie entirely in one subtree and not go through the root at all. Forgetting to consider that can lead to wrong answers. The brute force formula (max of through_root, diameter_left, diameter_right) or the global update in DFS ensures you account for all nodes as potential connecting points.

• Recomputing Values (Inefficiency): In a naive implementation, one might write a function to compute height and call it separately for every node’s left and right (like the brute force approach). Without caching, this causes heavy recomputation. This mistake doesn’t give a wrong answer, but it can time out for large trees (n up to 10,000). The optimal solution avoids this by computing heights in one pass.

• Global Variable Usage in Recursion: If you use a global (or static class member) to track diameter, be careful to reset it appropriately between test cases (especially in coding platforms where the same function might be called multiple times). In our implementations, we reset maxDiameter at the start of diameterOfBinaryTree in Java, and used a local nonlocal variable in Python to avoid issues. Forgetting to reset can cause one test’s result to carry over to the next.

• Not Handling Null Tree: Ensure your code returns 0 for an empty tree (null root). In this problem constraints, n>=1, so maybe you don’t get an empty input. But it’s good practice (and some variations or interviewer follow-ups might remove that guarantee). If root is None, diameter should be 0. Similarly, for a single-node tree, diameter is 0 (no edges).

Edge Cases to Consider:

• Single Node: As noted, the diameter of a single-node tree is 0, since there are no edges connecting two distinct nodes.

• Two Nodes: If the tree has two nodes (one root, one child), the diameter is 1 (one edge connecting them). This is the simplest non-trivial case.

• Skewed Tree (Linked-list shape): e.g., a tree where each node only has one child, forming a straight line. Here the diameter is the length of that line (which is n-1 edges for n nodes). Our DFS should handle this and return n-1. This is also the worst-case for recursion depth. For example, a chain of 4 nodes [1,2,null,3,null,4,null] should yield diameter 3 (as in Example 3).

• Balanced Tree: e.g., a perfect binary tree. Diameter in such cases often goes through the root (but not always if one subtree is taller than the other). Ensure logic doesn’t assume it must pass the root – it naturally doesn’t in our solutions, since we check all nodes.

• Tree with Diameter in Subtree: A tricky scenario is when the longest path doesn’t go through the root at all. For example, a tree where the left subtree itself has a very long path that’s longer than any path involving the root. Our approaches handle this by always propagating the best diameter up. If implementing manually, one might forget to compare the subtree’s internal diameter against the through-root path. The recursive patterns we discussed cover it by taking max of those values.

• Large Trees: With n = 10000, a DFS recursion should still be okay in Java and C++ (which can handle deep recursion if not tail but within limits). In Python, default recursion limit (~1000) might be exceeded if the tree is a 10,000-length chain. As an edge consideration in Python, one might need to set sys.setrecursionlimit to a higher value or use an iterative approach to avoid RecursionError. The problem constraints might assume a balanced enough tree or not consider Python’s limit in judging, but it’s worth mentioning if someone is implementing in Python.

Alternative Variations & Related Problems

This problem is a classic application of tree traversal and using post-order information (subtree heights) to compute a global property (diameter). There are several related problems and variations:

• Maximum Depth of Binary Tree (LeetCode 104): This asks for the height of the tree. It’s actually a sub-problem of what we do when computing diameter. In our solution, we computed heights of subtrees; the “maximum depth” is just the height of the root. Solving the diameter requires computing depths anyway. This relationship shows up in our formula.

• Balanced Binary Tree (LeetCode 110): This problem asks to check if the tree is height-balanced (difference between left and right subtree heights is at most 1 for every node). The approach also uses computing left and right heights for each node. It’s often solved with a similar DFS where you propagate heights up and check balance at each node. The techniques are analogous (post-order traversal), even though the end goal is different.

• Binary Tree Maximum Path Sum (LeetCode 124): Instead of counting edges, each node has a value and you want the path (not necessarily root-to-leaf, can be any two nodes) with the maximum sum of values. The structure of the solution is very similar to diameter: you calculate the best path through each node (which might include the node’s value plus the best gains from left and right sides) and track a global max. This is a more complex variation where you can’t simply count — you must consider negative values and decide whether to include a subtree or not. But conceptually, it’s about evaluating paths through each node and using DFS.

• Longest Univalue Path (LeetCode 687): This asks for the longest path where all nodes have the same value. The solution pattern is again a DFS that computes information from children and updates a global maximum. It’s like a constrained diameter: you only count edges where the node values match a certain condition. The recursion passes up the length of the path that can be extended through the parent (if the parent has the same value) and resets when the value changes. This is a nice twist on the diameter concept.

• Diameter of an N-ary Tree / General Tree: If you have a tree that’s not binary (nodes can have many children) or even just an undirected tree (graph with N nodes and N-1 edges), the definition of diameter is the same. The approaches can be extended. For an N-ary tree, a DFS solution would need to find the two largest child heights at each node (instead of just left and right) to compute the longest path through that node. For an undirected tree (graph), the two-pass BFS method described above is a common solution. It’s worth noting that the two-pass method is essentially finding diameter by finding a farthest point and then another farthest from that – this works because in a tree, a BFS will always reach one end of the longest path when started at the other end.

• Path Tracing Variations: Sometimes, an interview follow-up might ask not just for the length of the diameter but to return the actual nodes on the longest path or print the path. To do that, you’d need to record more information during your traversal. One approach is to store parent pointers (as we did conceptually for the BFS method) or augment the DFS to return not just the height but also the path or node contributing to that height. This complicates the code a bit: you could keep a global pointer to the node at which the diameter was found and maybe reconstruct the path by backtracking from that node to the two leaves. It’s an extension that requires careful bookkeeping.

Related practice problems: If you want to strengthen your understanding, here are some problems that use similar ideas or help build the intuition:

• 543. Diameter of Binary Tree – (The problem we just solved) Try implementing it in different ways or languages.

• 104. Maximum Depth of Binary Tree – (Easy) Compute height of a tree. A good warm-up for this problem.

• 110. Balanced Binary Tree – (Easy/Medium) Uses height computations to check balance property.

• 124. Binary Tree Maximum Path Sum – (Hard) Similar DFS pattern but working with sums instead of edge counts.

• 687. Longest Univalue Path – (Medium) DFS global path problem with a twist that values must match.

• 250. Count Univalue Subtrees – (Medium) Another DFS pattern where information (all nodes in subtree have same value or not) is passed up. Not a diameter, but a related tree DFS problem.

• Boundary Traversal of Binary Tree or Lowest Common Ancestor – These are different problems (traversal and LCA), but solving them will improve understanding of tree structures, which indirectly helps in reasoning about longest paths.