Introduction

LeetCode 543 – Diameter of Binary Tree is one of the most popular binary tree interview problems.

This problem teaches:

1. Depth First Search (DFS)
2. Tree height calculation
3. Recursive traversal
4. Bottom-up recursion
5. Tree optimization techniques

It is extremely important because it introduces a very common pattern in tree problems:

Use recursion to calculate subtree heights while simultaneously updating a global answer.

This same idea is used in:

1. Balanced Binary Tree
2. Maximum Path Sum
3. Longest ZigZag Path
4. Tree DP problems

Problem Link

🔗 https://leetcode.com/problems/diameter-of-binary-tree/

Problem Statement

Given the root of a binary tree:

Return:

The diameter is:

The length of the longest path between any two nodes in the tree.

This path:

1. May pass through the root
2. May not pass through the root

Important Note

The diameter is measured in:

not nodes.

Example 1

Input

Tree:

Output

Explanation:

Longest path:

Edges count:

Example 2

Input

Tree:

Output:

Understanding Diameter

At every node:

Possible longest path through that node is:

Why?

Because:

1. One side contributes left edges
2. Other side contributes right edges

Together they form a path.

Key Observation

For every node:

We compute this for all nodes.

Maximum among them becomes answer.

Brute Force Approach

Intuition

For every node:

1. Calculate left subtree height
2. Calculate right subtree height
3. Compute diameter
4. Recursively repeat for children

Brute Force Complexity

Height gets recalculated repeatedly.

Time Complexity

Space Complexity

where:

Optimized DFS Approach

Instead of separately calculating:

1. Height
2. Diameter

We calculate both in one DFS traversal.

Core Idea

While calculating subtree height:

We also update:

This avoids repeated traversal.

Java Solution

Cleaner Optimized Version

Why This Works

At every node:

1. Find left subtree height
2. Find right subtree height
3. Compute:

1. Update global maximum diameter
2. Return current subtree height upward

Dry Run

Input

Step 1

Leaf nodes:

Step 2

At node:

Left height:

Right height:

Diameter through node:

Update:

Height of node 2:

Step 3

At root:

Left height:

Right height:

Diameter:

Update:

Final Answer

Recursive Visualization

Diameter gets updated during return phase.

Time Complexity Analysis

Optimized DFS Solution

Time Complexity

because every node is visited once.

Space Complexity

where:

Worst case:

for skewed tree.

Brute Force vs Optimized

Interview Explanation

In interviews, explain:

While recursively calculating subtree heights, we simultaneously compute the maximum possible path passing through every node.

This demonstrates:

1. DFS understanding
2. Bottom-up recursion
3. Optimization skills
4. Tree DP thinking

Common Mistakes

1. Counting Nodes Instead of Edges

Diameter measures:

not nodes.

2. Forgetting Global Variable

Diameter must be updated across all nodes.

3. Returning Diameter Instead of Height

Recursive function should return:

not diameter.

FAQs

Q1. Does diameter always pass through root?

No.

It can exist completely inside a subtree.

Q2. Why use DFS?

Because height calculation naturally follows recursive depth traversal.

Q3. Why update diameter globally?

Because longest path may occur at any node.

Q4. Is this problem important for interviews?

Very important.

It is one of the most common recursive tree questions.

Conclusion

LeetCode 543 is one of the best problems for learning recursive tree optimization.

It teaches:

1. DFS traversal
2. Height calculation
3. Bottom-up recursion
4. Global answer tracking

The key insight is:

Diameter through a node equals left subtree height + right subtree height.

Once you understand this pattern, many advanced binary tree problems become much easier.