Bird
Raised Fist0
Interview Prepdp-advanced-trees-bitmaskeasyFacebookAmazonGoogle

Diameter of Binary Tree

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2)O(n) recursion stackYes (deep recursion)NoMention only - never code
3. Optimal Bottom-Up DFSO(n)O(n) recursion stackYesYes (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/5)
1. Consider the following iterative postorder traversal code to compute the maximum path sum in a binary tree. Given the tree below, what is the final value of max_sum after the function completes? Tree structure: ``` 1 / 2 3 ```
class TreeNode:
    def __init__(self, val=0, left=null, right=null):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    stack = []
    node = root
    last_visited = null
    gain_map = {}

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_gain = max(gain_map.get(peek.left, 0), 0)
                right_gain = max(gain_map.get(peek.right, 0), 0)
                current_path_sum = peek.val + left_gain + right_gain
                max_sum = max(max_sum, current_path_sum)
                gain_map[peek] = peek.val + max(left_gain, right_gain)
                last_visited = stack.pop()
    return max_sum
easy
A. 5
B. 4
C. 6
D. 3

Solution

  1. Step 1: Trace left subtree gain

    Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.
  2. Step 2: Trace root and right subtree

    Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sum of path 2 -> 1 -> 3 is 6 [OK]
Hint: Sum path 2->1->3 yields max sum 6 [OK]
Common Mistakes:
  • Ignoring one child's gain leads to 5 or 4
  • Off-by-one in gain_map updates
  • Returning partial sums instead of max path sum
2. What is the time complexity of the Morris preorder traversal algorithm on a binary tree with n nodes, and why might some candidates mistakenly think it is higher?
medium
A. O(n log n) because each node is visited multiple times during threading
B. O(n) but with O(n) auxiliary space due to recursion stack
C. O(n^2) because the inner loop to find predecessor can traverse many nodes repeatedly
D. O(n) because each edge is traversed at most twice during threading and restoration

Solution

  1. Step 1: Identify traversal of nodes and edges

    Each node is visited once, and each edge is traversed at most twice (once to create thread, once to remove it).
  2. Step 2: Explain why complexity is linear

    Because total edge traversals sum to O(n), the overall time complexity is O(n).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Threading and restoring links cause at most two visits per edge [OK]
Hint: Each edge visited max twice -> O(n) time [OK]
Common Mistakes:
  • Assuming inner loop causes O(n^2)
  • Confusing threading with recursion stack space
  • Thinking threading causes log n overhead
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. If the problem is modified so that the postorder traversal may contain duplicate values, which of the following changes is necessary to correctly reconstruct the tree?
hard
A. Modify the algorithm to store indices of all occurrences of each value in inorder and track usage to avoid ambiguity.
B. Use a hash map from value to index in inorder traversal as before, ignoring duplicates.
C. Switch to preorder and inorder traversals which do not have duplicates.
D. Use a greedy approach attaching nodes as left children to handle duplicates.

Solution

  1. Step 1: Understand the impact of duplicates

    Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.
  2. Step 2: Required modification

    Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.
  3. Step 3: Why other options fail

    Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking multiple indices per value is necessary for duplicates [OK]
Hint: Duplicates require tracking all indices, not just one [OK]
Common Mistakes:
  • Ignoring duplicates in hash map
  • Assuming unique values always
  • Switching traversal types incorrectly
5. Suppose the problem is extended: the tree nodes can have duplicate values, and you want to check if the tree is symmetric ignoring node values, only structure matters. Which modification to the original DFS approach correctly solves this variant?
hard
A. Keep the value comparison but add a hash map to track visited nodes to avoid duplicates.
B. Use BFS level-order traversal and check if each level forms a palindrome of node values.
C. Modify the base case to return true if both nodes are null, and skip the value comparison step entirely.
D. Perform a preorder traversal and compare the traversal list with its reverse.

Solution

  1. Step 1: Understand the variant ignores node values, only structure matters

    Therefore, the value comparison step must be removed to avoid false negatives due to duplicates.
  2. Step 2: Modify the DFS to only check if both nodes exist or are null, recursively comparing mirrored subtrees

    Return true if both nodes are null; otherwise, recurse on mirrored children without comparing values.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Ignoring values means skipping value checks but preserving mirrored structure checks [OK]
Hint: Ignore values, check only mirrored structure recursively [OK]
Common Mistakes:
  • Keeping value checks causing false negatives
  • Using BFS palindrome checks which fail on structure
  • Using preorder traversal which ignores mirrored structure
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