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. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

    1
   / \
  2   3

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result

easy

A. [2, 1, 3]

B. [1, 2, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Trace first iteration with current=1

   Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.

2. Step 2: Trace second iteration with current=2

   Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).

3. Step 3: Detect thread at 2.right=1

   Since predecessor.right == current, reset 2.right=None, move current=1.right=3.

4. Step 4: Trace current=3

   Node 3 has no left child, append 3, move current=3.right=None, loop ends.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Output matches preorder traversal [1,2,3] [OK]

Hint: Morris preorder appends root before left subtree [OK]

Common Mistakes:

• Appending nodes in wrong order
• Not resetting threaded links
• Confusing left and right child traversal

2. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?

easy

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Calculate tree height

   Height h = 3 (nodes 1 -> 2 -> 4).

2. Step 2: Binary search on last level nodes

   Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]

Hint: Count = perfect nodes + last level nodes found [OK]

Common Mistakes:

• Off-by-one in binary search bounds
• Miscounting last level nodes

3. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 5: rob_current calculation uses left[0] and right[0]

B. Line 7: Returning (rob_current, not_rob_current)

C. Line 6: not_rob_current uses max(left) + max(right)

D. Line 2: Base case returns (0, 0)

Solution

1. Step 1: Understand rob_current calculation

   rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.

2. Step 2: Identify the bug

   Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using rob values of children overcounts and breaks correctness [OK]

Hint: Rob current node + not_rob children, not rob children [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple
• Forgetting adjacency constraints

4. What is the space complexity of the optimized recursive DFS approach for checking if a binary tree is symmetric, assuming the tree has n nodes and height h?

medium

A. O(h) due to recursion stack depth proportional to tree height

B. O(1) since no extra space besides variables is used

C. O(n) because all nodes are stored in an auxiliary data structure

D. O(n) due to storing all nodes in a queue for BFS

Solution

1. Step 1: Identify recursion stack usage

   The recursive calls go as deep as the height of the tree, so the recursion stack uses O(h) space.

2. Step 2: Confirm no additional data structures store all nodes

   The algorithm does not use queues or arrays to store nodes; it only uses call stack and local variables.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack space depends on tree height, not total nodes [OK]

Hint: Recursion stack space = tree height, not total nodes [OK]

Common Mistakes:

• Confusing BFS queue space with DFS recursion stack
• Assuming O(n) space due to node storage
• Ignoring recursion stack space

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