Diameter of Binary Tree

Difficulty: Easy | Acceptance: 65.50% | Paid: No Topics: Tree, Depth-First Search, Binary Tree

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.

• Examples
• Constraints
• Brute Force DFS
• Optimized DFS

Examples

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].

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

Constraints

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

Brute Force DFS

Intuition For every node, the longest path passing through it is the sum of the heights of its left and right subtrees. We can iterate through every node, calculate the height of its left and right children, and track the maximum sum found.

Steps

• Define a helper function height(node) that returns the maximum depth of a tree rooted at node.
• Traverse the tree using DFS.
• For each node visited, calculate the potential diameter passing through it as height(node.left) + height(node.right).
• Update a global maximum diameter variable if this sum is greater than the current maximum.
• Return the global maximum after traversal completes.

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def height(node):
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))
        
        self.diameter = 0
        
        def dfs(node):
            if not node:
                return
            left_h = height(node.left)
            right_h = height(node.right)
            self.diameter = max(self.diameter, left_h + right_h)
            dfs(node.left)
            dfs(node.right)
            
        dfs(root)
        return self.diameter

Complexity

• Time: O(N²) - For each of the N nodes, we calculate the height, which takes O(N) in the worst case.
• Space: O(N) - Recursion stack space.
• Notes: Simple to understand but inefficient for large trees.

Optimized DFS

Intuition We can compute the height and the diameter in a single traversal. As we recursively calculate the height of the left and right subtrees for a node, we can simultaneously update the maximum diameter found so far using the sum of those two heights.

Steps

• Initialize a global variable diameter to 0.
• Define a recursive function dfs(node) that returns the height of the tree rooted at node.
• In the base case (null node), return 0.
• Recursively call dfs on the left and right children to get their heights.
• The potential diameter passing through the current node is left_height + right_height. Update the global diameter if this value is larger.
• Return the height of the current node: max(left_height, right_height) + 1.
• Call dfs(root) and return the global diameter.

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.diameter = max(self.diameter, left + right)
            return max(left, right) + 1
        
        dfs(root)
        return self.diameter

Complexity

• Time: O(N) - We visit every node exactly once.
• Space: O(N) - Recursion stack space in the worst case (skewed tree), O(log N) for balanced tree.
• Notes: Optimal solution, avoiding redundant calculations.