Diameter of Binary Tree

📋

Problem

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.

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

Edge cases: Single node tree → diameter is 0Skewed tree (all nodes only have one child) → diameter is n-1Complete binary tree → diameter is the longest path through root

</>

IDE

def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:public int diameterOfBinaryTree(TreeNode root)int diameterOfBinaryTree(TreeNode* root)function diameterOfBinaryTree(root)

def diameterOfBinaryTree(root):
    # Write your solution here
    pass

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int diameterOfBinaryTree(TreeNode* root) {
    // Write your solution here
    return 0;
}

function diameterOfBinaryTree(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to only checking root or empty tree case.✅ Add recursive DFS to compute heights and update max diameter at every node.

Wrong: Incorrect diameter for skewed trees (e.g., 3 instead of 4)Off-by-one error in height or diameter calculation, confusing nodes and edges count.✅ Define height as number of nodes; diameter as number of edges = height_left + height_right; carefully handle null children.

Wrong: Diameter equals height of treeConfusing diameter with height; diameter is longest path between any two nodes, not just root to leaf.✅ Track max diameter globally as max(left_height + right_height) at each node, not just height.

Wrong: TLE on large inputsUsing brute force approach with repeated height computations causing O(n^2) complexity.✅ Implement bottom-up DFS that computes height and diameter in one pass for O(n) time.

✓

Test Cases

Try testing your code on minimal and boundary inputs like empty or single node trees.

Consider tricky cases with multiple longest paths or skewed trees to catch subtle bugs.

Focus on optimizing your solution to run efficiently on large inputs by reducing redundant computations.

t1_01basic

Input{"root":[1,2,3,4,5]}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Think about the longest path between any two nodes in the tree.

💡 Use a DFS to compute heights of subtrees and track max diameter at each node.

💡 The diameter at a node is left subtree height + right subtree height; keep max over all nodes.

Why it failed: Returned diameter is incorrect; likely forgot to consider paths passing through nodes other than root. Fix by tracking max(left_height + right_height) at each node during DFS.

✓ Correctly computes diameter by considering all paths through nodes.

t1_02basic

Input{"root":[1,2,null,3,null,4,null,5]}

Expected4

⏱ Performance - must finish in 2000ms

Skewed tree with nodes 1->2->3->4->5; longest path length is 4 edges.

💡 Check how your code handles skewed trees where each node has only one child.

💡 Height of subtree is number of nodes down to leaf; diameter is max path between any two nodes.

💡 In skewed tree, diameter equals number of edges = number of nodes - 1.

Why it failed: Incorrect diameter for skewed tree; likely not handling single-child paths properly. Fix by ensuring height calculation works for null children and diameter updates accordingly.

✓ Correctly handles skewed trees and computes diameter as n-1.

t2_01edge

Input{"root":[1]}

Expected0

⏱ Performance - must finish in 2000ms

Single node tree has diameter 0 because there are no edges.

💡 Consider the base case of a tree with only one node.

💡 Diameter is the longest path between two nodes, so no edges means diameter 0.

💡 Return 0 when root has no children.

Why it failed: Returned non-zero diameter for single node tree; fix by returning 0 when root has no children.

✓ Correctly returns 0 for single node tree.

t2_02edge

Input{"root":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty tree (null root) has diameter 0 by definition.

💡 Check how your code handles an empty tree input (null root).

💡 Diameter of empty tree is 0 since no nodes or edges exist.

💡 Return 0 immediately if root is null.

Why it failed: Code crashes or returns non-zero for empty tree; fix by checking if root is null and returning 0.

✓ Correctly returns 0 for empty tree.

t2_03edge

Input{"root":[1,2,3,4,5,6,7]}

Expected4

⏱ Performance - must finish in 2000ms

Complete binary tree with 7 nodes; longest path is from leaf 4 to leaf 7 through root, length 4 edges.

💡 Test your code on a complete binary tree to verify longest path through root.

💡 Diameter is sum of heights of left and right subtrees at root.

💡 Ensure your code updates max diameter at every node, not just leaves.

Why it failed: Incorrect diameter for complete binary tree; likely only checking leaf-to-leaf paths or missing root paths. Fix by updating diameter at every node.

✓ Correctly computes diameter for complete binary tree.

t3_01corner

Input{"root":[1,2,3,4,null,null,5,6]}

Expected4

⏱ Performance - must finish in 2000ms

Tree with multiple longest paths of same length; diameter is 4 edges.

💡 Consider trees with multiple longest paths of equal length.

💡 Your code must track max diameter globally, not just first found.

💡 Update max diameter at every node considering left and right subtree heights.

Why it failed: Returned smaller diameter ignoring multiple longest paths; fix by tracking global max diameter during DFS.

✓ Correctly handles multiple longest paths and returns max diameter.

t3_02corner

Input{"root":[1,2,null,3,null,4,null,5,null,6]}

Expected5

⏱ Performance - must finish in 2000ms

Deep skewed tree to test off-by-one errors; diameter is 5 edges.

💡 Check for off-by-one errors in height and diameter calculations.

💡 Height counts nodes, diameter counts edges; diameter = height - 1 for skewed trees.

💡 Ensure height returns 0 for null nodes and adds 1 for current node.

Why it failed: Off-by-one error in diameter calculation; fix by correctly defining height and diameter relationship.

✓ Correctly computes diameter with no off-by-one errors.

t3_03corner

Input{"root":[1,2,3,4,5,6,7,8,null,null,null,null,null,null,9]}

Expected6

⏱ Performance - must finish in 2000ms

Tree with unbalanced subtrees to test greedy approach traps; diameter is 6 edges.

💡 Beware of greedy approaches that only consider longest path through root.

💡 Diameter may pass through nodes other than root; check all nodes.

💡 Use bottom-up DFS to compute max diameter globally.

Why it failed: Greedy approach failed by only considering root path; fix by computing diameter at every node.

✓ Correctly computes diameter considering all nodes.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large complete binary tree with n=100 nodes; O(n) solution must complete within 2 seconds.

💡 Brute force O(n^2) approach will time out on large inputs.

💡 Use bottom-up DFS to compute height and diameter in one pass.

💡 Avoid repeated height computations by caching results.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing O(n) bottom-up DFS solution.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following Python code implementing the optimal solution for the envelope nesting problem. Given the input [[5,4],[6,4],[6,7],[2,3]], what is the value of the list lis after processing all envelopes?

easy

A. [2, 3, 7]

B. [3, 4, 7]

C. [2, 3, 4, 7]

D. [3, 4]

Solution

1. Step 1: Sort envelopes by width ascending and height descending

   Sorted envelopes: [[2,3],[5,4],[6,7],[6,4]] -> heights = [3,4,7,4]

2. Step 2: Build LIS on heights

   Process heights: 3 -> lis=[3]; 4 -> lis=[3,4]; 7 -> lis=[3,4,7]; 4 -> replace lis[1] with 4 (no change). Final lis = [3,4,7]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final lis length 3 matches expected output [OK]

Hint: Trace LIS updates carefully with bisect_left [OK]

Common Mistakes:

• Misplacing elements in lis on equal heights
• Confusing bisect_left with bisect_right
• Not sorting heights correctly

2. 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

3. The following code attempts to solve the Russian Doll Envelopes problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes by width ascending and height ascending

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing element in lis at found index

Solution

1. Step 1: Examine sorting order

   Sorting by width ascending and height ascending causes envelopes with same width but increasing height to be counted incorrectly in LIS.

2. Step 2: Understand LIS requirement

   Heights must be sorted descending for equal widths to avoid counting invalid envelopes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order bug leads to wrong LIS and incorrect nesting count [OK]

Hint: Sort height descending for equal widths to avoid LIS errors [OK]

Common Mistakes:

• Sorting both dimensions ascending instead of height descending
• Misusing bisect functions
• Incorrectly extracting heights

4. What is the time complexity of the bottom-up bitmask DP solution for the shortest path visiting all nodes problem on a graph with n nodes?

medium

A. O(n * 2^n)

B. O(n^2 * 2^n)

C. O(n! * n)

D. O(2^n * E) where E is the number of edges

Solution

1. Step 1: Identify loops in the bottom-up DP

   The outer loop iterates over all masks (2^n), the inner loop over nodes (n), and for each node, we iterate over its neighbors (E edges total). Thus, the complexity depends on the number of edges.

2. Step 2: Confirm complexity formula

   Since each state dp[u][mask] is updated by checking neighbors, total complexity is O(2^n * E), where E is the number of edges.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches known complexity for bitmask DP on graphs [OK]

Hint: Complexity depends on subsets and edges, not just nodes squared [OK]

Common Mistakes:

• Confusing with O(n^2 * 2^n)
• Ignoring neighbor iteration
• Assuming factorial complexity

5. Suppose the House Robber III problem is modified so that you can rob the same node multiple times (i.e., unlimited reuse), but still cannot rob directly connected nodes in the same iteration. Which of the following changes to the algorithm is correct to handle this variant efficiently?

hard

A. Modify DP states to track how many times each node is robbed and use memoization accordingly

B. Use the same DP but multiply node values by the number of times robbed, no other changes needed

C. The problem reduces to a maximum weighted independent set on a tree with unlimited reuse, which is NP-hard, so no efficient solution exists

D. Transform the tree into a graph and run a maximum weighted matching algorithm

Solution

1. Step 1: Understand problem change

   Allowing multiple robberies per node requires tracking counts per node, not just binary rob/not_rob states.

2. Step 2: Adapt DP states

   DP must be extended to track how many times a node is robbed and ensure adjacency constraints per iteration, requiring more complex memoization.

3. Step 3: Reject incorrect options

   Simply multiplying values ignores adjacency constraints; problem remains polynomial on trees, so NP-hard claim is false; maximum weighted matching is unrelated.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Extended DP with counts handles reuse and adjacency constraints [OK]

Hint: Reusing nodes requires richer DP states, not just value scaling [OK]

Common Mistakes:

• Assuming problem becomes NP-hard or unchanged