Diameter of Binary Tree

🎯

Diameter of Binary Tree

easyDPFacebookAmazonGoogle

Imagine you want to find the longest path you can travel between any two points in a network of roads shaped like a tree. This problem asks you to find that longest path in a binary tree structure.

💡 This problem is about finding the longest path between any two nodes in a binary tree, which is not necessarily passing through the root. Beginners often struggle because the longest path might go through any node, not just the root, and they need to understand how to combine information from subtrees efficiently.

📋

Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

The number of nodes in the tree is in the range [1, 10^5]Node values are arbitrary and do not affect the diameter calculation

💡

Example

Input"root = [1,2,3,4,5]"

Output3

The longest path is [4,2,1,3] or [5,2,1,3], both have length 3 edges.

• Single node tree → diameter is 0
• Skewed tree (all nodes only have one child) → diameter is n-1
• Complete binary tree → diameter is the longest path through root
• Tree with multiple longest paths of same length → diameter is that length

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the longest path from the root or a single subtree fails because the diameter might pass through a node that is not the root, combining two longest paths from its left and right subtrees.

DP state:

dp[node] = the height of the subtree rooted at 'node', which is the longest path from 'node' down to a leaf.

Recurrence:diameter(node) = max(diameter(left), diameter(right), height(left) + height(right))

The diameter at a node is the maximum of the diameter in its left subtree, right subtree, or the path passing through the node connecting left and right heights.

⚠️

Common Mistakes

Assuming diameter passes through root only

Incorrect diameter returned when longest path is in a subtree

✅ Check diameter at every node, not just root

Recomputing height multiple times without memoization

Time limit exceeded on large inputs

✅ Use memoization or combine height and diameter calculation in one DFS

Returning number of nodes instead of edges for diameter

Off-by-one error in output

✅ Diameter is number of edges = sum of heights of left and right subtrees

Not handling null nodes properly in recursion

Runtime errors or incorrect results

✅ Add base case for null nodes returning height 0

Using global variables without resetting between calls

Incorrect results on multiple test cases

✅ Reset global diameter variable before each computation

🧠

Brute Force (Pure Recursion with Repeated Height Computations)

💡 This approach exists to show the naive way of solving the problem by directly implementing the definition, which helps understand the problem deeply before optimizing.

Intuition

For each node, compute the diameter by checking the longest path through it (sum of left and right subtree heights) and recursively compute diameters of left and right subtrees.

Algorithm

1. Define a function to compute the height of a subtree rooted at a node.
2. For each node, compute the diameter as the sum of heights of left and right subtrees.
3. Recursively compute the diameter for left and right subtrees.
4. Return the maximum diameter found.

💡 The challenge is that height computations are repeated many times, making the algorithm inefficient.

Recurrence:diameter(node) = max(diameter(left), diameter(right), height(left) + height(right))

</>

Code

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

def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

def diameterOfBinaryTree(root):
    if not root:
        return 0
    left_height = height(root.left)
    right_height = height(root.right)
    left_diameter = diameterOfBinaryTree(root.left)
    right_diameter = diameterOfBinaryTree(root.right)
    return max(left_height + right_height, max(left_diameter, right_diameter))

# Example usage:
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(diameterOfBinaryTree(root))  # Output: 3

Line Notes

def height(node):Defines a helper to compute subtree height, which is used repeatedly

if not node:Base case: height of empty subtree is 0

return 1 + max(height(node.left), height(node.right))Height is 1 plus max height of children

left_height = height(root.left)Compute left subtree height for diameter calculation

right_height = height(root.right)Compute right subtree height for diameter calculation

left_diameter = diameterOfBinaryTree(root.left)Recursively compute diameter in left subtree

right_diameter = diameterOfBinaryTree(root.right)Recursively compute diameter in right subtree

return max(left_height + right_height, max(left_diameter, right_diameter))Diameter is max of path through root or in subtrees

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        int leftDiameter = diameterOfBinaryTree(root.left);
        int rightDiameter = diameterOfBinaryTree(root.right);
        return Math.max(leftHeight + rightHeight, Math.max(leftDiameter, rightDiameter));
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        Solution sol = new Solution();
        System.out.println(sol.diameterOfBinaryTree(root)); // Output: 3
    }
}

Line Notes

public int height(TreeNode node)Helper method to compute height of subtree

if (node == null) return 0;Base case for empty subtree

return 1 + Math.max(height(node.left), height(node.right));Height is 1 plus max height of children

int leftHeight = height(root.left);Compute left subtree height for diameter

int rightHeight = height(root.right);Compute right subtree height for diameter

int leftDiameter = diameterOfBinaryTree(root.left);Recursively compute left subtree diameter

int rightDiameter = diameterOfBinaryTree(root.right);Recursively compute right subtree diameter

return Math.max(leftHeight + rightHeight, Math.max(leftDiameter, rightDiameter));Return max diameter among three candidates

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int height(TreeNode* node) {
    if (!node) return 0;
    return 1 + max(height(node->left), height(node->right));
}

int diameterOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    int leftDiameter = diameterOfBinaryTree(root->left);
    int rightDiameter = diameterOfBinaryTree(root->right);
    return max(leftHeight + rightHeight, max(leftDiameter, rightDiameter));
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    cout << diameterOfBinaryTree(root) << endl; // Output: 3
    return 0;
}

Line Notes

int height(TreeNode* node)Helper function to compute height of subtree

if (!node) return 0;Base case for empty subtree

return 1 + max(height(node->left), height(node->right));Height is 1 plus max height of children

int leftHeight = height(root->left);Compute left subtree height for diameter

int rightHeight = height(root->right);Compute right subtree height for diameter

int leftDiameter = diameterOfBinaryTree(root->left);Recursively compute left subtree diameter

int rightDiameter = diameterOfBinaryTree(root->right);Recursively compute right subtree diameter

return max(leftHeight + rightHeight, max(leftDiameter, rightDiameter));Return max diameter among three candidates

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function height(node) {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

function diameterOfBinaryTree(root) {
    if (!root) return 0;
    const leftHeight = height(root.left);
    const rightHeight = height(root.right);
    const leftDiameter = diameterOfBinaryTree(root.left);
    const rightDiameter = diameterOfBinaryTree(root.right);
    return Math.max(leftHeight + rightHeight, Math.max(leftDiameter, rightDiameter));
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3)
);
console.log(diameterOfBinaryTree(root)); // Output: 3

Line Notes

function height(node)Helper function to compute subtree height

if (!node) return 0;Base case for empty subtree

return 1 + Math.max(height(node.left), height(node.right));Height is 1 plus max height of children

const leftHeight = height(root.left);Compute left subtree height for diameter

const rightHeight = height(root.right);Compute right subtree height for diameter

const leftDiameter = diameterOfBinaryTree(root.left);Recursively compute left subtree diameter

const rightDiameter = diameterOfBinaryTree(root.right);Recursively compute right subtree diameter

return Math.max(leftHeight + rightHeight, Math.max(leftDiameter, rightDiameter));Return max diameter among three candidates

⏱

Complexity

TimeO(n^2)

SpaceO(n) due to recursion stack

For each node, height is computed recursively which itself is O(n), leading to O(n^2) in total for n nodes.

💡 For n=20 nodes, this means roughly 400 operations, which grows quickly and becomes inefficient for large trees.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is valuable to understand the problem and motivate optimization.

🧠

Optimal Bottom-Up DFS (Single Pass)

💡 This approach combines height and diameter calculation in a single DFS traversal, making it the most efficient and elegant solution.

Intuition

While computing the height of each node, simultaneously update the maximum diameter found so far by considering the sum of left and right subtree heights.

Algorithm

1. Define a recursive function that returns the height of a node.
2. At each node, recursively get left and right subtree heights.
3. Update a global or external variable with max diameter as left_height + right_height.
4. Return height as 1 + max(left_height, right_height).
5. After traversal, return the recorded max diameter.

💡 This approach avoids separate diameter and height computations by combining them, reducing complexity and code.

Recurrence:height(node) = 1 + max(height(left), height(right)); diameter = max(diameter, height(left) + height(right))

</>

Code

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

def diameterOfBinaryTree(root):
    diameter = 0
    def height(node):
        nonlocal diameter
        if not node:
            return 0
        left_height = height(node.left)
        right_height = height(node.right)
        diameter = max(diameter, left_height + right_height)
        return 1 + max(left_height, right_height)
    height(root)
    return diameter

# Example usage:
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(diameterOfBinaryTree(root))  # Output: 3

Line Notes

diameter = 0Initialize diameter to track max path length

def height(node):Helper function to compute height and update diameter

nonlocal diameterAllows updating diameter variable defined outside nested function

if not node:Base case: height of empty subtree is 0

diameter = max(diameter, left_height + right_height)Update diameter if current path is longer

return 1 + max(left_height, right_height)Return height of current node's subtree

height(root)Start DFS traversal from root

return diameterReturn the maximum diameter found

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        diameter = Math.max(diameter, leftHeight + rightHeight);
        return 1 + Math.max(leftHeight, rightHeight);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        Solution sol = new Solution();
        System.out.println(sol.diameterOfBinaryTree(root)); // Output: 3
    }
}

Line Notes

private int diameter = 0;Class variable to track max diameter

public int diameterOfBinaryTree(TreeNode root)Main function to start DFS and return diameter

private int height(TreeNode node)Helper function to compute height and update diameter

if (node == null) return 0;Base case for empty subtree

diameter = Math.max(diameter, leftHeight + rightHeight);Update diameter if current path is longer

return 1 + Math.max(leftHeight, rightHeight);Return height of current node's subtree

height(root);Start DFS traversal

return diameter;Return the maximum diameter found

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int diameter = 0;

int height(TreeNode* node) {
    if (!node) return 0;
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    diameter = max(diameter, leftHeight + rightHeight);
    return 1 + max(leftHeight, rightHeight);
}

int diameterOfBinaryTree(TreeNode* root) {
    diameter = 0;
    height(root);
    return diameter;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    cout << diameterOfBinaryTree(root) << endl; // Output: 3
    return 0;
}

Line Notes

int diameter = 0;Global variable to track max diameter

int height(TreeNode* node)Helper function to compute height and update diameter

if (!node) return 0;Base case for empty subtree

diameter = max(diameter, leftHeight + rightHeight);Update diameter if current path is longer

return 1 + max(leftHeight, rightHeight);Return height of current node's subtree

height(root);Start DFS traversal

return diameter;Return the maximum diameter found

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function diameterOfBinaryTree(root) {
    let diameter = 0;
    function height(node) {
        if (!node) return 0;
        const leftHeight = height(node.left);
        const rightHeight = height(node.right);
        diameter = Math.max(diameter, leftHeight + rightHeight);
        return 1 + Math.max(leftHeight, rightHeight);
    }
    height(root);
    return diameter;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3)
);
console.log(diameterOfBinaryTree(root)); // Output: 3

Line Notes

let diameter = 0;Variable to track max diameter

function height(node)Helper function to compute height and update diameter

if (!node) return 0;Base case for empty subtree

diameter = Math.max(diameter, leftHeight + rightHeight);Update diameter if current path is longer

return 1 + Math.max(leftHeight, rightHeight);Return height of current node's subtree

height(root);Start DFS traversal

return diameter;Return the maximum diameter found

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Each node is visited once, and height and diameter are computed simultaneously.

💡 For n=20 nodes, this means about 20 operations, making it very efficient.

Interview Verdict: Accepted / Optimal solution

This is the best approach to implement in interviews due to its efficiency and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal bottom-up DFS approach is recommended for interviews due to its efficiency and simplicity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
3. Optimal Bottom-Up DFS	O(n)	O(n) recursion stack	Yes	Yes (with modifications)	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when and how to present each during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding of the problem.Step 3: Discuss inefficiencies and introduce memoization to optimize.Step 4: Present the optimal single-pass DFS solution.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of tree traversal, recursion, optimization via memoization, and ability to combine computations efficiently.

Common Follow-ups

• How to find the actual longest path nodes? → Use parent pointers or reconstruct path during DFS.
• Can this be done iteratively? → Yes, with stack and postorder traversal but more complex.

💡 These follow-ups test deeper understanding and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves longest path in a tree, 2) Diameter or max distance asked, 3) Need to combine info from subtrees, 4) Overlapping subproblems in tree structure.

Signature Phrases

longest path between any two nodesdiameter of binary treepath may or may not pass through root

NOT This Pattern When

Problems asking for simple traversal or subtree sums without combining paths are not this pattern.

Similar Problems

Longest Path in a Tree - similar concept of combining subtree infoMaximum Depth of Binary Tree - height calculation is a subproblemBinary Tree Maximum Path Sum - similar bottom-up approach combining subtree results

Practice

1. Consider the following bottom-up DP code for TSP. Given the distance matrix below, what is the final returned value?

dist = [
  [0, 10, 15],
  [10, 0, 20],
  [15, 20, 0]
]

print(tsp_bottom_up(dist))

The code is:

def tsp_bottom_up(dist):
    n = len(dist)
    ALL_VISITED = (1 << n) - 1
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                for j in range(n):
                    if mask & (1 << j) and i != j:
                        prev_mask = mask ^ (1 << i)
                        dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])

    ans = float('inf')
    for i in range(1, n):
        ans = min(ans, dp[ALL_VISITED][i] + dist[i][0])
    return ans

easy

A. 45

B. 35

C. 40

D. 30

Solution

1. Step 1: Trace dp for mask=7 (all visited) and i=1,2

   Calculate dp[7][1] and dp[7][2] by considering previous states and distances.

2. Step 2: Compute final answer by adding dist back to start city

   Minimum cost is min(dp[7][1] + dist[1][0], dp[7][2] + dist[2][0]) = min(35 + 10, 20 + 15) = 30.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal TSP cost for given matrix is 30 [OK]

Hint: Final answer includes return to start city cost [OK]

Common Mistakes:

• Forgetting to add cost to return to start city

2. Consider the following buggy code for the House Robber III problem. Which line contains the subtle bug that causes incorrect results on some inputs?

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[1] + right[1]  # Bug here
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

medium

A. Line returning max of dfs(root) instead of sum

B. Line computing rob_node sums children rob values instead of not_rob values

C. Line returning (not_rob_node, rob_node) tuple instead of single value

D. Line checking if node is null and returning (0,0)

Solution

1. Step 1: Understand rob_node calculation

   When robbing current node, children cannot be robbed, so we must add left[0] and right[0] (not_rob values).

2. Step 2: Identify bug

   The code incorrectly adds left[1] and right[1] (rob values), causing double counting and invalid solutions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct rob_node uses not_rob children sums [OK]

Hint: Robbing node requires adding children's not_rob values [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple

3. The following code attempts to find the longest chain of pairs but contains a subtle bug. Identify the line causing incorrect results on some inputs.

medium

A. Line 10: Checking if pair[0] > current_end

B. Line 7: Initializing current_end to negative infinity

C. Line 4: Sorting pairs by their start values

D. Line 12: Updating current_end to pair[1]

Solution

1. Step 1: Analyze sorting step

   Sorting by start values does not guarantee optimal chain selection in greedy approach.

2. Step 2: Impact on chain selection

   Greedy selection after sorting by start can miss longer chains that sorting by end would find.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by end is required for correctness [OK]

Hint: Sort by end, not start, for greedy correctness [OK]

Common Mistakes:

• Sorting by start and expecting greedy to work
• Misunderstanding greedy selection criteria
• Assuming initialization or condition is faulty

4. The following code attempts to count the number of longest increasing subsequences using DP arrays. Identify the bug that causes incorrect counting of LIS.

medium

A. counts array is initialized with zeros instead of ones

B. lengths array should be initialized with zeros instead of ones

C. The condition nums[j] < nums[i] should be nums[j] <= nums[i]

D. The final sum should be over counts where lengths are less than max_len

Solution

1. Step 1: Check initialization of counts array

   Counts represent number of LIS ending at each index; initially each element alone forms LIS of length 1, so counts[i] must start at 1, not 0.

2. Step 2: Consequence of zero initialization

   With counts initialized to 0, counts[i] remains 0 unless updated, causing undercounting of LIS and incorrect final result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initialize counts with 1 to count single-element subsequences [OK]

Hint: Counts must start at 1 to count single elements [OK]

Common Mistakes:

• Initializing counts with zeros
• Using <= instead of <
• Summing counts incorrectly

5. Suppose pairs can be reused multiple times in the chain (i.e., you can select the same pair multiple times if it fits). Which modification to the algorithm correctly finds the longest chain length under this new constraint?

hard

A. Use the same greedy approach sorting by end time, but allow pairs with start >= current_end

B. Use a bottom-up DP without sorting, checking all pairs for chain extension

C. Sort pairs by start time and greedily select pairs with earliest start repeatedly

D. Use dynamic programming with memoization to explore all sequences allowing reuse

Solution

1. Step 1: Understand reuse breaks greedy assumptions

   Greedy relies on no reuse; allowing reuse requires exploring multiple sequences.

2. Step 2: Use DP with memoization

   DP can handle repeated pairs by caching results for each state, ensuring correctness.

3. Step 3: Reject naive greedy and unsorted DP

   Greedy fails with reuse; unsorted DP is inefficient and incorrect without sorting.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Memoized DP handles reuse correctly [OK]

Hint: Reuse breaks greedy; DP needed [OK]

Common Mistakes:

• Trying to fix greedy by relaxing conditions
• Ignoring sorting or memoization in DP
• Assuming bottom-up DP without sorting suffices