Diameter of Binary Tree | Leetcode 543

Welcome to our deep dive on Diameter of a Binary Tree (Leetcode 543). This is an excellent problem to practice recursive Depth-First Search (DFS) patterns where you need to track global state while simultaneously computing local subtree paths.

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.

Example: Input: root = [1,2,3,4,5] Output: 3 (Explanation: The longest path could be 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3, both having 3 edges)

Approach: Recursive DFS (Bottom-Up) O(N)

Any path in a binary tree essentially connects the deepest leaf node of some left subtree to the deepest leaf node of some right subtree, joining them at a mutual "peak" or "parent" node.

The diameter passing through any given node N is fundamentally calculated as: Diameter(N) = Max_Depth(N.left) + Max_Depth(N.right)

Therefore, we can simply run a DFS algorithm that processes nodes "bottom-up" (Post-Order Traversal):

1. For every node, recursively ask its left child to calculate its maximum downward depth.
2. Ask its right child to calculate its maximum downward depth.
3. Once we have both values, we combine them: left_depth + right_depth. This is the local diameter acting as if the current node was the peak. We update our global max_diameter if this local sum is bigger.
4. Then, to satisfy our parent's recursive call, we must return the maximum contiguous downward depth we ourselves furnish: 1 + max(left_depth, right_depth).

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        
        def dfs(node):
            if not node:
                return 0
                
            left = dfs(node.left)
            right = dfs(node.right)
            
            # Update global diameter if this path is the longest seen so far
            self.max_diameter = max(self.max_diameter, left + right)
            
            # Return max depth path down to parent
            return 1 + max(left, right)
            
        dfs(root)
        return self.max_diameter

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (543)