Diameter of Binary Tree

Learn how to calculate the diameter (longest path) of a binary tree in one pass using recursion. Clear, step-by-step code and explanations perfect for LeetCode practice. You can solve the problem by visiting this Problem Link.

What the Problem Asks

LeetCode 543: Diameter of Binary Tree
Given a binary tree, find the length of the diameter of the tree.
The diameter is the number of edges on the longest path between any two nodes in the tree.

Key point: The longest path might go through the root or any other node.

Example Tree:

     1
    / \
   2   3
  / \
 4   5

The longest path is 4 → 2 → 1 → 3, which has 3 edges. So the diameter is 3.

How We’ll Solve It

1. Calculate Height and Track Diameter at Once
   • For each node, find the height of its left subtree and right subtree.
   • A path that passes through this node has length leftHeight + rightHeight (in edges).
   • Keep a global diameter variable and update it whenever leftHeight + rightHeight is bigger.
2. Recursive Height Function
   • Returns the height of the subtree (in nodes).
   • While returning, it also updates the diameter.

This way, we only walk the tree once (O(N) time), and we don’t need extra data structures.

Code Implementation

class Solution:
    diameter = 0  # holds the maximum diameter found

    def calculateHeight(self, root):
        # Base case: empty tree has height 0
        if not root:
            return 0

        # Recursively find heights of left and right subtrees
        leftHeight = self.calculateHeight(root.left)
        rightHeight = self.calculateHeight(root.right)

        # Update diameter: path through root uses leftHeight + rightHeight edges
        self.diameter = max(self.diameter, leftHeight + rightHeight)

        # Return the height of this subtree (in nodes)
        return 1 + max(leftHeight, rightHeight)

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # Initialize diameter and start recursion
        self.diameter = 0
        self.calculateHeight(root)
        return self.diameter

Step-By-Step Explanation

1. Global Variable diameter
   • We store the largest sum of left and right subtree heights (in edges).
2. calculateHeight(root)
   • If root is None, height is 0.
   • Otherwise:
     • Compute leftHeight = calculateHeight(root.left).
     • Compute rightHeight = calculateHeight(root.right).
     • Update diameter with leftHeight + rightHeight if it’s larger.
     • Return 1 + max(leftHeight, rightHeight) as the subtree height.
3. diameterOfBinaryTree(root)
   • Reset diameter to 0.
   • Call calculateHeight(root).
   • Return the final diameter.

This works because every node gets a chance to consider the path that goes through it. The longest such path anywhere in the tree is our answer.

Dry Run on Example

       1
      / \
     2   3
    / \
   4   5

1. calculateHeight(4) → left and right are None → heights 0,0 → diameter = max(0,0) → returns 1
2. calculateHeight(5) → same → returns 1
3. At node 2:
   • leftHeight=1, rightHeight=1 → diameter = max(0,1+1)=2
   • returns 1 + max(1,1)=2
4. calculateHeight(3) → returns 1
5. At node 1:
   • leftHeight=2, rightHeight=1 → diameter = max(2,2+1)=3
   • returns 1 + max(2,1)=3

Final diameter = 3.

Time & Space Complexity

• Time: O(N) — we visit each node once.
• Space: O(H) — recursion stack up to tree height H (worst-case O(N) for skewed tree, O(log N) for balanced tree).

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.