Problem Statement

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.

Additional information

• The number of nodes in the tree is in the range [1, 104].
• -100 <= Node.val <= 100

Example 1:

Input: root = [1, 2, 3, 4, 5]
Output: 3
Explanation: 3 is the length of the path [4, 2, 1, 3] or [5, 2, 1, 3].

Example 2:

Input: root = [1, 2]
Output: 1

Brute Force (Iterative + Recursion)

Intuition
The diameter of a tree is simply the maximum value of (left_height + right_height) calculated for every single node in the tree.
A straightforward (but inefficient) way to solve this is to traverse every node in the tree. For each node we visit, we explicitly calculate the height of its left and right subtrees to find the longest path passing through that specific node. We then take the maximum of these values.

Algorithm

1. Define a helper function get_height(node) that traverses down to leaves to find the height.
2. Traverse the entire tree (e.g., using a queue for BFS or a stack).
3. For every node curr:

• Calculate left_h = get_height(curr.left).
• Calculate right_h = get_height(curr.right).
• Update max_diameter = max(max_diameter, left_h + right_h).

4. Return max_diameter.

def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    
    max_diameter = 0
    
    # Helper to calculate height of a specific node
    def get_height(node):
        if not node:
            return 0
        return 1 + max(get_height(node.left), get_height(node.right))
    
    # Traverse every node in the tree
    stack = [root]
    while stack:
        node = stack.pop()
        
        # Calculate diameter passing strictly through THIS node
        left_h = get_height(node.left)
        right_h = get_height(node.right)
        
        max_diameter = max(max_diameter, left_h + right_h)
        
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
            
    return max_diameter

Time & Space Complexity

• Time complexity: O(n²)

• Reason: For every node n, we call get_height which takes O(n) time. Doing this for all n nodes results in O(n²).

• Space complexity: O(n)

• Reason: Stack space for traversal.

Depth-First Search (Optimized Recursive)

Intuition
The Brute Force approach is slow because it recalculates heights repeatedly. We can optimize this by calculating the height and the diameter in a single traversal (Bottom-Up).
When our recursive function returns the height of a node to its parent, we can simultaneously use that height to calculate the diameter passing through the current node (left_height + right_height) and update a global maximum.

Algorithm

1. Initialize a variable self.diameter (or a nonlocal variable) to 0.
2. Define a DFS function that returns the height of the current node.
3. Inside DFS:

• Recursively get left_height and right_height.
• Key Step: Update the global diameter: diameter = max(diameter, left_height + right_height).
• Return the height to the parent: 1 + max(left_height, right_height).

def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
    diameter = 0
    
    def height(node):
        nonlocal diameter
        if not node:
            return 0
        
        left_h = height(node.left)
        right_h = height(node.right)
        
        # The path through this node is left_h + right_h
        diameter = max(diameter, left_h + right_h)
        
        # Return the height of the node itself
        return 1 + max(left_h, right_h)
        
    height(root)
    return diameter

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node exactly once.

• Space complexity: O(h)

• Reason: The recursion stack depends on the height of the tree.