Problem Description

You're given the root of a binary tree and need to find the diameter of the tree.

The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path is measured by counting the number of edges between the nodes.

Key points to understand:

• The longest path might pass through the root node, but it doesn't have to
• The path length is counted as the number of edges (not nodes)
• You need to find the maximum possible path length between any two nodes in the entire tree

For example, if you have a tree where the longest path goes from a leaf in the left subtree, up through some parent nodes, and down to a leaf in the right subtree, that total edge count would be the diameter.

The solution works by using a depth-first search (DFS) approach. For each node, it:

1. Calculates the maximum depth of the left subtree (l)
2. Calculates the maximum depth of the right subtree (r)
3. The potential diameter through this node is l + r (sum of left and right depths)
4. Updates the global maximum diameter if this path is longer
5. Returns 1 + max(l, r) to represent the depth from this node to its parent

The ans variable keeps track of the maximum diameter found across all nodes, and this is returned as the final answer.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart leads us directly to using Depth-First Search.

Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach for solving the diameter of binary tree problem.

This makes sense because:

1. We need to explore the entire tree to find the longest path
2. For each node, we need to calculate the depth of its left and right subtrees
3. DFS naturally allows us to traverse to the leaf nodes first and then bubble up the depth information
4. As we return from recursive calls, we can compute the diameter at each node by adding the left and right depths
5. The recursive nature of DFS perfectly matches the recursive structure of the tree

Intuition

The key insight is that the longest path in a tree must have two endpoints, and these endpoints must be leaf nodes (or the root if it has only one child). Any longest path can be thought of as going "up" from one leaf to some common ancestor node, then "down" to another leaf.

For any node in the tree, if we consider it as the "peak" or "turning point" of a path, the longest path through that node would be:

• The deepest path in its left subtree + The deepest path in its right subtree

This is because we want to go as deep as possible on the left side, then turn at this node, and go as deep as possible on the right side.

So our strategy becomes:

1. For each node, calculate how deep we can go in its left subtree
2. Calculate how deep we can go in its right subtree
3. The diameter through this node = left depth + right depth
4. Keep track of the maximum diameter seen so far

But here's the clever part: while we're calculating potential diameters, we also need to return depth information to parent nodes. When returning to a parent, we can only take one path (either left or right), so we return 1 + max(left_depth, right_depth) to indicate the maximum depth from that node.

This way, in a single DFS traversal, we accomplish two things:

• Calculate the diameter at each node (by summing left and right depths)
• Return the depth information needed by parent nodes to calculate their diameters

The beauty of this approach is that we only visit each node once, making it an efficient O(n) solution.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

We implement the solution using DFS (Depth-First Search) with a helper function that serves dual purposes: calculating depths and updating the diameter.

Implementation Details:

1. Main Function Setup:

   • Initialize a variable ans = 0 to track the maximum diameter found
   • Call the DFS helper function starting from the root
   • Return the final answer

2. DFS Helper Function: The dfs function takes a node and returns the maximum depth from that node to any leaf in its subtree.

   Base Case:

   • If the node is None, return 0 (no depth)

   Recursive Case:

   • Recursively calculate the maximum depth of the left subtree: l = dfs(root.left)
   • Recursively calculate the maximum depth of the right subtree: r = dfs(root.right)

   Update Global Maximum:

   • The diameter through the current node is l + r (sum of depths from both sides)
   • Update the global answer: ans = max(ans, l + r)
   • We use nonlocal ans to modify the outer scope variable

   Return Value:

   • Return 1 + max(l, r) to the parent
   • The 1 represents the edge from current node to its parent
   • max(l, r) gives the longer path to choose when going up to the parent

3. Why This Works:

   • Each node is visited exactly once during the traversal
   • At each node, we calculate the potential diameter if the longest path passes through it
   • The global maximum tracks the best diameter found across all nodes
   • The return value ensures parent nodes get correct depth information for their calculations

Time Complexity: O(n) where n is the number of nodes, as we visit each node once

Space Complexity: O(h) where h is the height of the tree, due to the recursion call stack

Example Walkthrough

Let me walk through a concrete example to illustrate how this solution works.

Consider this binary tree:

        1
       / \
      2   3
     / \
    4   5

Step-by-step execution:

1. Start at root (node 1):

   • First, we need to get depths from left and right subtrees
   • Call dfs(node 2) for left subtree

2. At node 2:

   • Call dfs(node 4) for left child

3. At node 4 (leaf):

   • Left child is None → l = 0
   • Right child is None → r = 0
   • Diameter through node 4: l + r = 0 + 0 = 0
   • Update ans = max(0, 0) = 0
   • Return to parent: 1 + max(0, 0) = 1

4. Back at node 2:

   • Left depth from node 4: l = 1
   • Now call dfs(node 5) for right child

5. At node 5 (leaf):

   • Left child is None → l = 0
   • Right child is None → r = 0
   • Diameter through node 5: l + r = 0
   • ans remains 0
   • Return to parent: 1 + max(0, 0) = 1

6. Back at node 2 (completing):

   • Left depth: l = 1 (from node 4)
   • Right depth: r = 1 (from node 5)
   • Diameter through node 2: l + r = 1 + 1 = 2
   • Update ans = max(0, 2) = 2
   • Return to parent: 1 + max(1, 1) = 2

7. Back at root (node 1):

   • Left depth from node 2: l = 2
   • Now call dfs(node 3) for right child

8. At node 3 (leaf):

   • Left child is None → l = 0
   • Right child is None → r = 0
   • Diameter through node 3: l + r = 0
   • ans remains 2
   • Return to parent: 1 + max(0, 0) = 1

9. Back at root (node 1, completing):

   • Left depth: l = 2 (from node 2)
   • Right depth: r = 1 (from node 3)
   • Diameter through node 1: l + r = 2 + 1 = 3
   • Update ans = max(2, 3) = 3
   • Return: 1 + max(2, 1) = 3 (not used since this is root)

Final answer: 3

The longest path is: node 4 → node 2 → node 1 → node 3, which has 3 edges.

Notice how:

• At each node, we calculate the potential diameter by summing left and right depths
• The maximum diameter (3) occurs at the root node in this case
• Each node returns its depth to help parent nodes calculate their diameters
• We only traverse each node once, making this efficient

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the algorithm performs constant time operations: calculating the maximum value, updating the answer variable, and returning the height. Since we visit all n nodes exactly once and perform O(1) work at each node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, the binary tree is completely unbalanced (essentially a linked list), where all nodes are arranged in a single path. This would result in a recursion depth of n, requiring O(n) space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but we consider the worst-case scenario for space complexity analysis, which is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Node Count vs Edge Count

One of the most frequent mistakes is counting nodes instead of edges when calculating the diameter. The problem specifically asks for the number of edges in the longest path, not the number of nodes.

Incorrect Approach:

def diameterOfBinaryTree(self, root):
    self.max_diameter = 0
  
    def dfs(node):
        if not node:
            return 0
      
        left = dfs(node.left)
        right = dfs(node.right)
      
        # WRONG: Adding 1 for the current node when updating diameter
        self.max_diameter = max(self.max_diameter, left + right + 1)
      
        return 1 + max(left, right)
  
    dfs(root)
    return self.max_diameter

Why it's wrong: Adding 1 when calculating the diameter counts the current node, making it a node count rather than an edge count.

Correct Approach:

# The diameter through current node is simply left + right (edges only)
self.max_diameter = max(self.max_diameter, left + right)

2. Using Local Variable Instead of Instance/Nonlocal Variable

Attempting to use a local variable to track the maximum diameter won't work because integers are immutable in Python, and the variable won't be accessible across recursive calls.

Incorrect Approach:

def diameterOfBinaryTree(self, root):
    max_diameter = 0  # Local variable
  
    def dfs(node):
        if not node:
            return 0
      
        left = dfs(node.left)
        right = dfs(node.right)
      
        # This won't work - can't modify local variable from outer scope
        max_diameter = max(max_diameter, left + right)  # UnboundLocalError
      
        return 1 + max(left, right)
  
    dfs(root)
    return max_diameter

Solutions:

Option 1 - Use instance variable (shown in solution):

self.max_diameter = 0  # Instance variable accessible throughout

Option 2 - Use nonlocal keyword:

def diameterOfBinaryTree(self, root):
    max_diameter = 0
  
    def dfs(node):
        nonlocal max_diameter  # Declare nonlocal to modify outer variable
        # ... rest of the code

Option 3 - Use a mutable container:

def diameterOfBinaryTree(self, root):
    max_diameter = [0]  # List is mutable
  
    def dfs(node):
        # ... calculate left and right
        max_diameter[0] = max(max_diameter[0], left + right)
        # ...
  
    dfs(root)
    return max_diameter[0]

3. Forgetting to Handle Single Node or Empty Tree

While the provided solution handles these cases correctly through the base case, beginners might write solutions that don't properly handle edge cases.

Potential Issue:

• Empty tree (root = None): Should return 0
• Single node tree: Should return 0 (no edges)
• Tree with only two nodes: Should return 1 (one edge)

Verification: Always test your solution with these minimal cases to ensure the base case and return values are correct.