Domain 1EasyCORE

Diameter of Binary Tree

The problem asks us to find the diameter of a binary tree, which is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the `root`. The length of a path is measured by the number of edges between the nodes.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

543. Diameter of Binary Tree

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 49.5%


Problem Breakdown

The problem asks us to find the diameter of a binary tree, which is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length of a path is measured by the number of edges between the nodes.

Inputs:

  • root: The root node of the binary tree.

Outputs:

  • An integer representing the length of the diameter of the tree.

Implicit Constraints and Edge Cases:

  • The tree can be empty (though the problem guarantees at least one node).
  • The tree can have negative values in its nodes.
  • The solution should handle up to 10,000 nodes efficiently.

Intuition

A brute-force approach would involve checking all pairs of nodes to find the longest path between them. This approach is computationally expensive with a time complexity of O(n^2), where n is the number of nodes in the tree, making it impractical for large trees.

The key insight is that the diameter of a binary tree can be determined by finding the maximum sum of the depths of the left and right subtrees for each node. This reduces the problem to a single traversal of the tree, resulting in a time complexity of O(n).

Approach

  1. Define a Helper Function: Create a recursive function that computes the depth of a subtree and updates the diameter if the path through the current node is longer than previously recorded.
  2. Compute Depth: For each node, compute the depth of its left and right subtrees.
  3. Update Diameter: The diameter at the current node is the sum of the depths of its left and right subtrees. Update the global maximum diameter if this value is greater than the previously recorded maximum.
  4. Return Depth: Return the depth of the current subtree, which is 1 plus the maximum depth of its left or right subtree.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack, which can be as deep as the height of the tree.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameterOfBinaryTree(root: TreeNode) -> int:
    def depth_and_diameter(node: TreeNode) -> (int, int):
        if not node:
            return 0, 0
        
        # Recursively find the depth of the left and right subtrees
        left_depth, left_diameter = depth_and_diameter(node.left)
        right_depth, right_diameter = depth_and_diameter(node.right)
        
        # The diameter at this node is the sum of the depths of its subtrees
        current_diameter = left_depth + right_depth
        
        # Update the maximum diameter found so far
        max_diameter = max(left_diameter, right_diameter, current_diameter)
        
        # Return the depth of the current subtree and the maximum diameter found
        return 1 + max(left_depth, right_depth), max_diameter
    
    _, result = depth_and_diameter(root)
    return result

Edge Cases Handled

  • Single Node Tree: The function correctly returns a diameter of 0 for a tree with only one node.
  • Balanced Tree: Handles trees where the left and right subtrees are balanced.
  • Skewed Tree: Handles trees that are heavily skewed to one side, such as a linked list-like structure.
  • Negative Node Values: The function correctly processes nodes with negative values without any issues.