Bird
Raised Fist0
Interview Prepdp-advanced-trees-bitmaskeasyFacebookAmazonGoogle

Diameter of Binary Tree

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"root":[1,2,3,4,5]}
Expected3

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

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

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

t2_01edge
Input{"root":[1]}
Expected0

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

t2_02edge
Input{"root":[]}
Expected0

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

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

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

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

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

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

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

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

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

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]}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?
def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited != peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result
easy
A. [2, 3, 1]
B. [1, 3, 2]
C. [3, 2, 1]
D. [3, 1, 2]

Solution

  1. Step 1: Trace traversal on given tree

    Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.
  2. Step 2: Process nodes in postorder

    3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Output matches postorder [3, 2, 1] [OK]
Hint: Postorder output for this tree is [3,2,1] [OK]
Common Mistakes:
  • Confusing order of appending nodes
  • Off-by-one in stack popping
2. Examine the following buggy code snippet for computing the maximum path sum in a binary tree. Which line contains the subtle bug that causes incorrect results on trees with negative node values?
def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max_gain(node.left)
        right_gain = max_gain(node.right)
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)
        # Bug: returns sum of both left and right gains to parent
        return node.val + left_gain + right_gain

    max_gain(root)
    return max_sum
medium
A. Line returning 0 for null node
B. Line computing current_path_sum = node.val + left_gain + right_gain
C. Line updating max_sum = max(max_sum, current_path_sum)
D. Line returning node.val + left_gain + right_gain

Solution

  1. Step 1: Understand return value meaning

    The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).
  2. Step 2: Identify the bug

    Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Return should be node.val + max(left_gain, right_gain) [OK]
Hint: Return value must be single path gain, not sum of both children [OK]
Common Mistakes:
  • Returning sum of both children gains
  • Ignoring negative gains
  • Updating max_sum incorrectly
3. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?
medium
A. Line creating root node with postorder[-1]
B. Line initializing inorder_index to 0
C. Line attaching node as right child
D. Line popping from stack inside while loop

Solution

  1. Step 1: Identify inorder_index initialization

    inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.
  2. Step 2: Consequences of wrong initialization

    Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Correct inorder_index initialization is critical for stack popping logic [OK]
Hint: inorder_index must start at last index, not zero [OK]
Common Mistakes:
  • Wrong inorder_index initialization
  • Confusing postorder traversal direction
  • Incorrect stack popping conditions
4. Examine the following buggy code for the Path Sum problem. Which line contains the subtle bug that causes incorrect results on some inputs?
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if curr_sum == targetSum:  # Bug here
            return True
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)
medium
A. Line 3: if not node: return False
B. Line 6: if curr_sum == targetSum:
C. Line 8: return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
D. Line 5: curr_sum += node.val

Solution

  1. Step 1: Understand leaf node condition

    The sum should be checked only at leaf nodes, not at every node.
  2. Step 2: Identify the bug

    Line 6 checks sum at any node, causing premature True returns for partial paths.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Bug causes incorrect True if partial path sum equals targetSum [OK]
Hint: Sum check must be at leaf nodes only [OK]
Common Mistakes:
  • Checking sum at internal nodes
  • Not handling null root
5. Suppose the Path Sum problem is modified so that node values can be negative, and you want to find if any root-to-leaf path sums exactly to targetSum. Which of the following changes to the DFS approach is necessary to handle this correctly?
hard
A. Precompute all path sums and store them in a hash set for O(1) lookup
B. Add memoization to avoid revisiting nodes with the same current sum
C. Use BFS instead of DFS to guarantee shortest path sum
D. Remove early stopping because negative values can invalidate pruning assumptions

Solution

  1. Step 1: Understand impact of negative values

    Negative values mean partial sums can decrease later, so pruning based on current sum is unsafe.
  2. Step 2: Adjust algorithm accordingly

    Early stopping based on partial sums must be removed to avoid missing valid paths.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Negative values break pruning assumptions, so early stopping must be disabled [OK]
Hint: Negative values invalidate pruning, so no early stopping [OK]
Common Mistakes:
  • Assuming early stopping always works
  • Switching to BFS unnecessarily
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard