LeetCode Solutions Blog

Diameter of Binary Tree

Number: 543

Difficulty: Easy

Paid? No

Problem Description

Given the root of a binary tree, return the length of the diameter of the tree. The diameter is defined as the number of edges in the longest path between any two nodes in the tree. Note that this path may or may not pass through the root.

Key Insights

Use depth-first search (DFS) to explore the tree.
The diameter at a node is the sum of the depths of its left and right subtrees.
Track the maximum diameter found during the DFS traversal.
Recursively calculating the depth of subtrees provides an efficient solution.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(n), in the worst-case scenario due to the recursion stack (skewed tree).

Solution

The solution employs a DFS traversal of the binary tree. At every node in the tree, compute the depth of the left and right subtrees. The sum of these depths gives the potential diameter (longest path through that node). Update a global maximum diameter variable if this sum exceeds the current maximum. Finally, return the maximum diameter after completing the DFS.

Code Solutions

# 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: TreeNode) -> int:
        # Global variable to track the maximum diameter found
        self.max_diameter = 0
        
        def dfs(node):
            # Base case: if node is None, depth is 0.
            if not node:
                return 0
            # Compute the depth of left and right subtrees.
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)
            # Update the global diameter: the path through this node
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            # Return the depth of the tree rooted at this node.
            return max(left_depth, right_depth) + 1
        
        dfs(root)
        return self.max_diameter