Diameter of Binary Tree Solution in Java

The diameter of a binary tree represents the longest path between any two nodes in the tree. This solution presents an efficient approach to calculate this diameter using depth-first search with O(n) time complexity.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input tree be empty, or is it guaranteed to have at least one node?
2. Are we allowed to modify the input tree structure during computation, or must we preserve it?
3. What is the expected time complexity for the solution? Should we aim for O(n) or can we accept O(n²)?
4. Do we need to return the diameter value itself, or should we also return the path that achieves it?
5. What is the maximum expected size of the tree? Will we be dealing with very large trees?

Restatement in my own words: Given a binary tree, I need to find the diameter of that tree. The diameter is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root, and the length is measured by the number of edges in the path.

Clarification of inputs, outputs, and constraints:

• Input: A binary tree represented by its root node (TreeNode), where each node has a value and optional left/right child pointers
• Output: An integer representing the diameter (number of edges in longest path)
• Constraints:
  • Tree can have 0 to 10,000 nodes (based on typical FAANG constraints)
  • Node values are integers in range [-100, 100]
  • The tree structure is immutable (we shouldn't modify it)

Assumptions I'm making:

• The tree is a standard binary tree with at most two children per node
• The diameter is measured in edges, not nodes (a single node has diameter 0)
• We're looking for the maximum path length between any two nodes in the tree

Data shape and hidden structure: The problem involves a hierarchical data structure where each node has a local property (height) that can be used to compute global properties (diameter). The key insight is that for any node, the diameter passing through it equals the sum of its left and right subtree heights. This creates a recursive structure where we can compute local information (heights) to derive global information (diameter).

2. Pattern Recognition

The problem asks us to find the diameter of a binary tree, which is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

Most likely pattern: The problem exhibits characteristics of a tree traversal with maximum tracking pattern, specifically requiring us to compute a property (diameter) that depends on the height of subtrees.

Wording that signals the pattern:

• "Longest path between any two nodes" - This suggests we need to consider all possible paths in the tree, not just those through the root
• "Diameter" - This is a classic tree metric that requires computing height information at each node
• "Between any two nodes" - Indicates we're looking for a global maximum across all possible node pairs

Why this problem fits that pattern: The key insight is that for any node in the tree, the diameter passing through that node equals the sum of the heights of its left and right subtrees. This transforms the problem from a global optimization over all node pairs to a local computation at each node, where we track the maximum such sum.

Core insight needed to solve it: The diameter of a binary tree is the maximum of:

1. The diameter of the left subtree
2. The diameter of the right subtree
3. The longest path passing through the root (sum of left and right heights)

This suggests we need to compute the height of each subtree while simultaneously tracking the maximum diameter encountered so far, making it a classic "post-order traversal with state tracking" problem.

The pattern is also reminiscent of the maximum path sum problems in trees, where we compute local values that contribute to a global optimum.

3. Approach Evolution

My first instinct is to think about the diameter as the longest path between any two nodes in the tree. A naive approach would be to compute the height of each node's left and right subtrees, then calculate the sum of those heights for every node, keeping track of the maximum. This would be O(n²) because for each node, we'd need to compute its subtree heights recursively.

But that's inefficient because we're recomputing the same subtree heights multiple times. Let me think about how to optimize this.

I notice that if I compute the diameter during the height calculation, I can avoid redundant computations. The key insight is that for any node, the diameter passing through it is the sum of the heights of its left and right subtrees. If I compute the height while tracking the maximum diameter seen so far, I can do this in one pass.

The core invariant I need to maintain is that at each node, I return the height of that subtree while updating a global maximum diameter value. This way, each node's subtree is processed exactly once.

Let me trace through this approach:

1. For each node, compute the height of left and right subtrees
2. The diameter through that node is left_height + right_height
3. Keep track of the maximum such diameter across all nodes
4. Return the maximum diameter found

This is O(n) time complexity because we visit each node exactly once, and the space complexity is O(h) where h is the height due to recursion stack.

The approach works because we're essentially computing the maximum path that goes through each node, and the overall diameter is simply the maximum of all such paths. This is a classic "post-order" traversal pattern where we process children before the parent node.

The key optimization is combining height calculation with diameter tracking in a single pass rather than computing them separately.

4. Data Structure Choice

For this problem, I'll use the standard TreeNode structure from binary tree problems, which is a simple class with value, left, and right pointers.

Primary data structures:

• TreeNode - The basic tree node structure with value, left, and right children
• int - To track the maximum diameter found so far

Why each data structure is needed:

• TreeNode is essential because it represents the fundamental unit of our input data structure - a binary tree. Each node contains the necessary information to traverse and compute path lengths.
• int is needed to maintain the global maximum diameter during our recursive traversal, allowing us to avoid having to return multiple values from each recursive call.

Time and space impact:

• The TreeNode structure uses O(1) space per node, which is unavoidable for representing the tree structure
• The int variable uses O(1) space to store our result, which is minimal overhead
• The recursive call stack will use O(h) space where h is the height of the tree, which is O(log n) for a balanced tree and O(n) for a skewed tree

Helper structure:

• No additional helper structures are needed beyond what's required to represent the tree itself. The solution uses a single recursive function that computes both height and diameter simultaneously, avoiding any need for additional containers or data structures.

The key insight is that we don't need to store intermediate path information - we just need to compute the height of each subtree and use that to calculate the diameter at each node, making our solution clean and efficient with minimal data structure overhead.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Consider this binary tree:

    1
   / \
  2   3
 / \
4   5

Step 1: Start at root node 1. We recursively process left and right subtrees.

• Left subtree: node 2 with children 4 and 5
• Right subtree: node 3

Step 2: Process left subtree (node 2).

• Process left child (node 4): returns height 1
• Process right child (node 5): returns height 1
• Height of node 2 = max(1,1) + 1 = 2
• Diameter through node 2 = left_height + right_height = 1 + 1 = 2

Step 3: Process right subtree (node 3).

• Node 3 has no children, so returns height 0
• Diameter through node 3 = 0 + 0 = 0

Step 4: Process root (node 1).

• Left subtree height = 2, right subtree height = 0
• Height of node 1 = max(2,0) + 1 = 3
• Diameter through node 1 = 2 + 0 = 2

Step 5: Track maximum diameter seen so far.

• Diameter through node 1: 2
• Diameter through node 2: 2
• Diameter through node 3: 0
• Maximum diameter = 2

The algorithm correctly identifies that the longest path is between nodes 4 and 5, passing through node 2, with a total of 2 edges.

The key insight is that for each node, we compute both its height and the diameter passing through it, then keep track of the global maximum. The algorithm handles edge cases like empty trees (returns 0) and single nodes (returns 0) naturally through the recursive structure.

public class DiameterOfBinaryTree {
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0; // Reset for each call
        getHeight(root);
        return maxDiameter;
    }
    
    private int getHeight(TreeNode node) {
        if (node == null) return 0;
        
        // Recursively get heights of left and right subtrees
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        
        // Calculate diameter passing through current node
        int currentDiameter = leftHeight + rightHeight;
        
        // Update global maximum diameter
        maxDiameter = Math.max(maxDiameter, currentDiameter);
        
        // Return height of current node (max depth + 1)
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

6. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int diameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        // Handle edge case of null root
        if (root == null) {
            return 0;
        }
        
        // Start DFS traversal to calculate diameter
        dfs(root);
        return diameter;
    }
    
    /**
     * Returns the height of the tree rooted at 'node'
     * While calculating, updates the maximum diameter found so far
     */
    private int dfs(TreeNode node) {
        // Base case: null node has height 0
        if (node == null) {
            return 0;
        }
        
        // Recursively get the height of left and right subtrees
        int leftHeight = dfs(node.left);
        int rightHeight = dfs(node.right);
        
        // The diameter passing through current node is sum of left and right heights
        // Update global maximum if this diameter is larger
        diameter = Math.max(diameter, leftHeight + rightHeight);
        
        // Return the height of current subtree (1 + max of left and right heights)
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

The solution uses a depth-first search approach where we calculate the height of each subtree while simultaneously tracking the maximum diameter found so far. For each node, we compute the sum of the heights of its left and right subtrees, which represents the longest path passing through that node. The algorithm efficiently computes both height and diameter in a single traversal, making it optimal for this problem.

7. Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the binary tree.

The algorithm performs a single post-order traversal of the binary tree, visiting each node exactly once. For each node, the work done is constant - computing the height and updating the maximum diameter. Since we process each node once and perform O(1) work per node, the overall time complexity is linear in the number of nodes.

Space Complexity: O(H) where H is the height of the binary tree, which is O(log N) for a balanced tree and O(N) in the worst case of a skewed tree.

The space complexity is dominated by the recursion stack used during the post-order traversal. In the worst case (skewed tree), the recursion depth could be N, leading to O(N) space complexity. In a balanced binary tree, the recursion depth is O(log N), resulting in O(log N) space usage.

The algorithm is optimal because:

1. We must examine each node at least once to determine the diameter
2. The solution avoids redundant computations by calculating height and diameter simultaneously during a single traversal
3. No additional data structures are needed beyond the recursion stack
4. The time complexity matches the theoretical lower bound of O(N) for tree traversal problems

This is near-optimal since we cannot do better than O(N) time complexity for this problem, and our space usage is optimal for the recursive approach.

8. Edge Cases & Pitfalls

Edge cases that need special handling:

1. Empty tree: When root is null, the diameter should be 0
2. Single node: A tree with only root node has diameter 0 (no edges)
3. Skewed trees: Trees where all nodes form a single path (like a linked list) - these can cause issues with height calculations
4. Duplicate values: The algorithm should work correctly even when nodes have identical values

Common implementation pitfalls:

1. Incorrect height calculation: Using Math.max(leftHeight, rightHeight) + 1 instead of Math.max(leftHeight, rightHeight) + 1 for the diameter calculation can lead to wrong results. The diameter through a node is leftHeight + rightHeight, not leftHeight + rightHeight + 1.

2. Not tracking global maximum: If using a local variable to track the maximum diameter, it might not be updated correctly when traversing different branches.

3. Integer overflow: In very large trees, the sum of two large heights could cause integer overflow, though this is less likely in typical constraints.

4. Misunderstanding the definition: Confusing diameter with height of the tree - diameter is the longest path between any two nodes, which may or may not pass through the root.

5. Not handling negative heights: If we don't properly handle the case where one side is null, we might get incorrect height values.

// Example of problematic approach:
// int diameter = Math.max(leftHeight, rightHeight) + 1; // Wrong!
// Should be: int diameter = leftHeight + rightHeight; // Correct!

9. Alternative Approaches

There are several alternative approaches to solving the diameter of binary tree problem, each with different trade-offs:

1. Brute Force Approach - O(n²) time complexity Instead of computing height and diameter together, we could compute the diameter for each node by:

• For each node, calculate the height of its left and right subtrees
• The diameter through that node is left_height + right_height
• Return the maximum such diameter across all nodes

This approach would require computing the height for each node multiple times, leading to O(n²) time complexity. While simple to understand and implement, it's inefficient for large trees.

2. Two-Pass DFS - O(n) time but more complex We could make two separate passes:

• First pass to find the height of each node (post-order traversal)
• Second pass to compute diameters using precomputed heights

This approach requires maintaining additional height information for each node, making the implementation more complex than our single-pass solution.

3. Global Variable Approach - O(n) time, less clean Instead of returning both height and diameter from each recursive call, we could use a global variable to track the maximum diameter found so far. This makes the recursive function simpler but introduces side effects that reduce code clarity and testability.

4. Iterative Approach - O(n) time, O(h) space We could convert the recursive solution to an iterative one using a stack, but this would be significantly more complex to implement correctly and wouldn't provide any major advantages over the clean recursive solution.

The chosen approach is preferred because it's clean, efficient, and maintains a single pass through the tree while avoiding side effects. The key insight is that we can compute both height and diameter simultaneously in one traversal, making it optimal in both time and space complexity.

10. Test Cases

// Test case 1: Basic balanced tree
//       1
//      / \
//     2   3
//    / \
//   4   5
// Diameter = 3 (path: 4->2->1->3 or 5->2->1->3)
TreeNode root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
root1.left.right = new TreeNode(5);

// Test case 2: Skewed tree
//   1
//    \
//     2
//      \
//       3
//        \
//         4
// Diameter = 3 (path: 1->2->3->4)
TreeNode root2 = new TreeNode(1);
root2.right = new TreeNode(2);
root2.right.right = new TreeNode(3);
root2.right.right.right = new TreeNode(4);

// Test case 3: Single node
//   1
// Diameter = 0
TreeNode root3 = new TreeNode(1);

// Test case 4: Empty tree
// Diameter = 0
TreeNode root4 = null;

// Test case 5: Complex tree with multiple paths
//       1
//      / \
//     2   3
//    / \   \
//   4   5   6
//      / \
//     7   8
// Diameter = 4 (path: 7->5->2->1->3->6)
TreeNode root5 = new TreeNode(1);
root5.left = new TreeNode(2);
root5.right = new TreeNode(3);
root5.left.left = new TreeNode(4);
root5.left.right = new TreeNode(5);
root5.right.right = new TreeNode(6);
root5.left.right.left = new TreeNode(7);
root5.left.right.right = new TreeNode(8);

The test cases cover:

• A balanced binary tree with a clear diameter path
• A right-skewed tree that tests the edge case of maximum depth on one side
• A single node (edge case with zero diameter)
• An empty tree (edge case with null root)
• A complex tree where the longest path goes through multiple branches

Each test case verifies different aspects of the algorithm including:

• Path calculation through left and right subtrees
• Handling of skewed trees where one side is much longer
• Edge case handling for minimal inputs
• Correct calculation of the maximum diameter across all possible paths

11. Final Summary

The diameter of a binary tree is the length of the longest path between any two nodes in the tree, where path length is measured by the number of edges. The solution works by recognizing that for each node, the diameter passing through it is the sum of the heights of its left and right subtrees. By computing this for every node and tracking the maximum, we efficiently find the overall diameter in a single traversal. This approach is optimal because it computes both subtree heights and maximum diameter simultaneously, avoiding redundant calculations and achieving O(n) time complexity with O(h) space complexity where h is the tree height. The key insight is that we don't need to find the actual longest path nodes, just compute the maximum possible diameter through any node in the tree.