Diameter of Binary Tree

Problem

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.

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

Constraints:

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

Solution

Approach: DFS with Diameter Tracking

The key insight is that the diameter at any node is the sum of the heights of its left and right subtrees. We calculate height recursively while tracking the maximum diameter seen.

Implementation

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0

        def height(node):
            if not node:
                return 0

            # Get heights of left and right subtrees
            left_height = height(node.left)
            right_height = height(node.right)

            # Update diameter if path through this node is longer
            self.diameter = max(self.diameter, left_height + right_height)

            # Return height of this subtree
            return 1 + max(left_height, right_height)

        height(root)
        return self.diameter

Alternative (Without Self Variable):

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0, 0  # (height, diameter)

            left_height, left_diameter = dfs(node.left)
            right_height, right_diameter = dfs(node.right)

            # Diameter through this node
            current_diameter = left_height + right_height

            # Max diameter in subtree
            max_diameter = max(current_diameter, left_diameter, right_diameter)

            # Height of this subtree
            height = 1 + max(left_height, right_height)

            return height, max_diameter

        return dfs(root)[1]

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(h), where h is the height of the tree (recursion stack).

Key Insights

Diameter Through Node: The diameter of a path through a node equals the sum of heights of its left and right subtrees. This represents the longest path that goes through that node.
Diameter May Not Pass Through Root: The longest path might be entirely in the left or right subtree, not passing through the root. We must check all nodes.
Height vs Diameter: While calculating height (depth), we simultaneously check if the diameter through each node is the maximum.
Post-Order Traversal: We compute heights of children before computing the parent’s diameter, following post-order traversal.
Edge Count: The diameter is the number of edges, not nodes. A path with n nodes has n-1 edges, which is why we add heights (edge counts) directly.