LeetCode 543 - Diameter of Binary Tree

The problem asks us to compute the diameter of a binary tree. The diameter is defined as the length of the longest path between any two nodes, measured in number of edges. Importantly, this path does not need to pass through the root of the tree.

leetcodeeasytreedepth-first-searchbinary-tree

LeetCode Problem 543

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to compute the diameter of a binary tree. The diameter is defined as the length of the longest path between any two nodes, measured in number of edges. Importantly, this path does not need to pass through the root of the tree. In other words, the path can lie entirely within the left subtree, right subtree, or span across the root.

The input is the root of a binary tree, which may contain up to 10,000 nodes, and node values can range from -100 to 100. The output is a single integer representing the diameter of the tree. The constraints indicate that we must consider performance carefully because naive solutions that repeatedly traverse subtrees could be too slow for large trees.

Important edge cases include a tree with a single node, which has a diameter of 0, and unbalanced trees where the longest path does not pass through the root.

Approaches

The brute-force approach would involve checking the longest path for every node. For each node, we could compute the height of its left and right subtrees, then sum them to get the longest path passing through that node. Repeating this for all nodes results in a lot of redundant computation, because subtree heights are recalculated multiple times. This leads to a time complexity of O(n^2) in the worst case for skewed trees.

The optimal approach leverages a single post-order depth-first search (DFS) traversal to calculate both the height of subtrees and the maximum diameter simultaneously. The key insight is that the longest path passing through a node is the sum of the heights of its left and right children. By updating a global maximum diameter during recursion, we only need one traversal to get the correct result, reducing the time complexity to O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Computes height for every node multiple times; slow for large trees
Optimal O(n) O(h) Single DFS traversal, updates global maximum; h is the tree height

Algorithm Walkthrough

  1. Define a global variable max_diameter initialized to 0. This variable will store the maximum diameter found during traversal.

  2. Implement a recursive DFS function that computes the height of a subtree rooted at a given node. Height is defined as the number of edges in the longest path from the node down to a leaf.

  3. For each node in the DFS:

  4. Recursively compute the left subtree height.

  5. Recursively compute the right subtree height.

  6. Update max_diameter as the maximum of its current value and the sum of left and right heights. This represents the longest path passing through the current node.

  7. Return the height of the current node as 1 plus the maximum of the left and right heights.

  8. Call DFS starting from the root.

  9. Return max_diameter after traversal completes.

Why it works: At each node, we consider the longest path that passes through it. Because the DFS traversal ensures that all subtrees are processed before their parent, we always have correct heights available to compute local diameters. This guarantees that the maximum diameter across the entire tree is found.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        
        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            left_height = dfs(node.left)
            right_height = dfs(node.right)
            self.max_diameter = max(self.max_diameter, left_height + right_height)
            return 1 + max(left_height, right_height)
        
        dfs(root)
        return self.max_diameter

Implementation walkthrough: The dfs function returns the height of a node, while simultaneously updating self.max_diameter with the longest path found at that node. Base case returns 0 for null nodes. For each node, we compute left and right heights, update the diameter, and propagate the height upward. This ensures a single traversal suffices.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0

    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftHeight := dfs(node.Left)
        rightHeight := dfs(node.Right)
        if leftHeight+rightHeight > maxDiameter {
            maxDiameter = leftHeight + rightHeight
        }
        return 1 + max(leftHeight, rightHeight)
    }

    dfs(root)
    return maxDiameter
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Go-specific notes: Go requires handling nil pointers explicitly, and integers do not overflow in this scenario. A helper max function is used instead of Python's built-in max.

Worked Examples

Example 1: root = [1,2,3,4,5]

Node Left Height Right Height Max Diameter
4 0 0 0
5 0 0 0
2 1 1 2
3 0 0 2
1 2 1 3

Final output: 3

Example 2: root = [1,2]

Node Left Height Right Height Max Diameter
2 0 0 0
1 1 0 1

Final output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once in DFS
Space O(h) Maximum recursion depth equals tree height h; O(n) worst-case for skewed tree

The complexity is efficient even for the maximum constraint of 10,000 nodes.

Test Cases

# test cases
assert Solution().diameterOfBinaryTree(None) == 0  # empty tree
assert Solution().diameterOfBinaryTree(TreeNode(1)) == 0  # single node
assert Solution().diameterOfBinaryTree(TreeNode(1, TreeNode(2))) == 1  # two nodes
assert Solution().diameterOfBinaryTree(TreeNode(1, TreeNode(2), TreeNode(3))) == 2  # simple balanced
assert Solution().diameterOfBinaryTree(TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))) == 3  # example 1
Test Why
None Handles empty tree, returns 0
TreeNode(1) Single node diameter is 0
TreeNode(1, TreeNode(2)) Diameter is 1 for two-node tree
TreeNode(1, TreeNode(2), TreeNode(3)) Small balanced tree
TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3)) Verifies example with diameter passing through root

Edge Cases

The first edge case is a single-node tree, where the diameter must be 0. The algorithm handles this correctly by returning 0 when both left and right heights are 0.

The second edge case is a skewed tree, where all nodes are only on one side (like a linked list). In this case, the diameter equals the number of nodes minus 1. The algorithm still works because DFS calculates heights correctly along the chain.

The third edge case is a tree where the longest path does not pass through the root. For example, a tree with a deep left subtree and a deep right subtree that does not share the root node. The global max_diameter ensures that all possible node pairs are considered, so the maximum path is captured correctly regardless of whether it passes through the root.