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 code implementing the optimal House Robber III solution. Given the tree: 3 / \ 2 3 \ \ 3 1 What is the value of rob_current when dfs is called on the root node (value 3)?

easy

A. 7

B. 6

C. 8

D. 9

Solution

1. Step 1: Trace dfs on left child (value 2)

   dfs(2) calls dfs(null) and dfs(3). dfs(null) returns (0,0). dfs(3) returns (3,0) because it has no children. So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(0,0)=0. dfs(3) returns (3,0). For node 2: rob_current=2+0+0=2, not_rob_current=max(0,3)+max(0,0)=3. dfs(2) returns (2,3).

2. Step 2: Trace dfs on right child (value 3)

   dfs(3) calls dfs(null) and dfs(1). dfs(1) returns (1,0). So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(1,0)=1. dfs(3) returns (3,1).

3. Step 3: Calculate rob_current at root (value 3)

   rob_current = 3 + left[1] + right[1] = 3 + 3 + 1 = 7.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sum matches known example output 7 [OK]

Hint: Add node.val + not_rob of children for rob_current [OK]

Common Mistakes:

• Mixing rob and not_rob values for children
• Off-by-one in recursion returns

2. You are given a binary tree and a target sum. The task is to find all root-to-leaf paths where the sum of the node values equals the target sum. Which algorithmic approach guarantees finding all such paths efficiently?

easy

A. Greedy traversal choosing the child with the closest value to the remaining sum

B. Depth-first search (DFS) with path tracking and backtracking to explore all root-to-leaf paths

C. Dynamic programming to store sums at each node and combine results bottom-up

D. Breadth-first search (BFS) with queue to find the shortest path matching the sum

Solution

1. Step 1: Understand problem requires all root-to-leaf paths

   Since we must find all paths, not just one, exhaustive exploration is needed.

2. Step 2: Identify DFS with path tracking and backtracking

   DFS explores each path fully, tracking the current path and sum, backtracking to explore alternatives.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS explores all paths, greedy or BFS do not guarantee all paths [OK]

Hint: All root-to-leaf paths require exhaustive DFS [OK]

Common Mistakes:

• Thinking greedy or BFS finds all paths
• Confusing DP for path enumeration

3. What is the time complexity of the optimized recursive solution that uses a hash map for index lookup when constructing a binary tree from inorder and postorder traversals of size n?

medium

A. O(n) because each node is processed once and index lookup is O(1)

B. O(n^2) due to repeated slicing of arrays

C. O(n log n) because of balanced tree recursion depth

D. O(n) but with O(n) auxiliary space for recursion stack and hash map

Solution

1. Step 1: Analyze time complexity

   Using a hash map avoids repeated linear searches, so each node is processed once -> O(n) time.

2. Step 2: Analyze space complexity

   Hash map stores n elements, recursion stack can be up to O(n) in skewed trees, so total auxiliary space is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is O(n), space includes recursion stack and hash map [OK]

Hint: Hash map reduces search to O(1), recursion stack adds O(n) space [OK]

Common Mistakes:

• Assuming slicing causes O(n^2) time
• Ignoring recursion stack space
• Confusing balanced tree depth with complexity

4. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total

medium

A. Line with 'if not node:' return statement

B. Line adding current_number to self.total

C. Line checking if node is leaf

D. Line calling dfs on node.right

Solution

1. Step 1: Understand when sums should be added

   Sum should only include complete root-to-leaf numbers, so addition must happen only at leaf nodes.

2. Step 2: Identify incorrect addition

   Adding current_number at every node (including non-leaf) causes partial numbers to be summed, inflating total incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum only at leaves fixes the bug [OK]

Hint: Add to total only at leaf nodes [OK]

Common Mistakes:

• Adding partial path sums at non-leaf nodes
• Not resetting total between calls

5. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?

hard

A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.

B. Use the brute force approach checking all paths from every node without prefix sums.

C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.

D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

1. Step 1: Understand path direction relaxation

   Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.

2. Step 2: Model tree as undirected graph and run DFS from every node

   To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Undirected DFS from every node with prefix sums counts all connected paths [OK]

Hint: Undirected graph DFS needed for arbitrary path directions [OK]

Common Mistakes:

• Trying to reuse one-directional prefix sum DFS without modification
• Assuming running DFS twice covers all paths
• Trying to store both directions in one prefix sum map