Diameter of Binary Tree in DSA Java

Mental Model

The diameter is the longest path between any two nodes in the tree, which may or may not pass through the root.

Analogy: Imagine a tree as a network of roads connecting cities (nodes). The diameter is the longest possible route you can travel between any two cities without repeating roads.

      1
     / \
    2   3
   / \
  4   5

Here, arrows show parent to child connections.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5

Goal: Find the longest path between any two nodes in the tree

Step 1: Calculate height of node 4 (leaf)

Node 4 height = 0

Why: Leaf nodes have height 0, base case for recursion

Step 2: Calculate height of node 5 (leaf)

Node 5 height = 0

Why: Leaf nodes have height 0, base case for recursion

Step 3: Calculate height of node 2 using heights of 4 and 5

Node 2 height = max(0,0) + 1 = 1

Why: Height is max child height plus one for current node

Step 4: Calculate height of node 3 (leaf)

Node 3 height = 0

Why: Leaf node height is 0

Step 5: Calculate height of node 1 using heights of 2 and 3

Node 1 height = max(1,0) + 1 = 2

Why: Height is max child height plus one

Step 6: Calculate diameter at node 2 as sum of heights of 4 and 5 plus 2 edges

Diameter at node 2 = 0 + 0 + 2 = 2

Why: Longest path through node 2 connects 4 and 5

Step 7: Calculate diameter at node 1 as max of left diameter, right diameter, and path through node 1

Diameter at node 1 = max(2,0, 1 + 0 + 2) = 3

Why: Longest path may pass through root connecting deepest nodes in left and right subtrees

Result:

Diameter = 3 (path: 4 -> 2 -> 1 -> 3)

Annotated Code

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class DiameterBinaryTree {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return maxDiameter;
    }

    private int height(TreeNode node) {
        if (node == null) return -1; // base case: empty node height

        int leftHeight = height(node.left); // height of left subtree
        int rightHeight = height(node.right); // height of right subtree

        int diameterThroughNode = leftHeight + rightHeight + 2; // path through current node
        if (diameterThroughNode > maxDiameter) {
            maxDiameter = diameterThroughNode; // update max diameter if larger
        }

        return Math.max(leftHeight, rightHeight) + 1; // height of current node
    }

    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);

        DiameterBinaryTree solution = new DiameterBinaryTree();
        System.out.println(solution.diameterOfBinaryTree(root));
    }
}

if (node == null) return -1; // base case: empty node height

return -1 for null to count edges correctly

int leftHeight = height(node.left); // height of left subtree

recursively get left subtree height

int rightHeight = height(node.right); // height of right subtree

recursively get right subtree height

int diameterThroughNode = leftHeight + rightHeight + 2; // path through current node

calculate diameter passing through current node

if (diameterThroughNode > maxDiameter) { maxDiameter = diameterThroughNode; }

update max diameter if current path is longer

return Math.max(leftHeight, rightHeight) + 1; // height of current node

return height for parent calculations

Output

3

Complexity Analysis

Time: O(n) because we visit each node once to calculate height and diameter

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach recalculates heights repeatedly causing O(n^2) time; this optimized method calculates height and diameter in one pass

Edge Cases

Empty tree (root is null)

Returns diameter 0 since no nodes exist

DSA Java

if (node == null) return -1;

Single node tree

Diameter is 0 because no edges exist

DSA Java

int diameterThroughNode = leftHeight + rightHeight + 2;

Tree with only left or only right children

Diameter equals height of the longest path down the single branch

DSA Java

return Math.max(leftHeight, rightHeight) + 1;

When to Use This Pattern

When asked for longest path between any two nodes in a tree, use the diameter pattern by combining subtree heights and tracking max path length.

Common Mistakes

Mistake: Returning 0 for null nodes instead of -1, causing off-by-one errors in diameter calculation
Fix: Return -1 for null nodes to count edges correctly between nodes

Mistake: Calculating height and diameter separately causing repeated work and slower code
Fix: Calculate height and update diameter in the same recursive function

Summary

Finds the longest path between any two nodes in a binary tree.

Use when you need the maximum distance between nodes, not just root to leaf paths.

The diameter can pass through any node, so track max path using left and right subtree heights.

Practice

1. What does the diameter of a binary tree represent?

easy

A. The number of leaf nodes in the tree

B. The length of the longest path between any two nodes in the tree

C. The height of the tree

D. The total number of nodes in the tree

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes, which may or may not pass through the root.

2. Step 2: Differentiate from other tree properties

   Height is the longest path from root to leaf, leaf count is number of leaves, total nodes is size, none of which define diameter.

3. Final Answer:

   The length of the longest path between any two nodes in the tree -> Option B

4. Quick Check:

   Diameter = Longest path between nodes [OK]

Hint: Diameter is longest path between any two nodes [OK]

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of edges
• Assuming diameter must pass through root

2. Which of the following Java method signatures correctly represents a recursive function to find the diameter of a binary tree node?

easy

A. public int diameter(int root)

B. public void diameter(TreeNode root)

C. public String diameter(TreeNode root)

D. public int diameter(TreeNode root)

Solution

1. Step 1: Identify correct parameter type

   The method must accept a TreeNode object representing the root of the tree or subtree.

2. Step 2: Identify correct return type

   Diameter is a number (int), so return type should be int, not void or String.

3. Final Answer:

   public int diameter(TreeNode root) -> Option D

4. Quick Check:

   Method returns int and takes TreeNode [OK]

Hint: Diameter method returns int and takes TreeNode [OK]

Common Mistakes:

• Using void return type for diameter
• Passing int instead of TreeNode
• Returning String instead of int

3. Given the following binary tree code snippet, what is the diameter of the tree?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int x) { val = x; }
}

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);

// Diameter calculation code omitted for brevity

medium

A. 2

B. 5

C. 3

D. 4

Solution

1. Step 1: Visualize the tree structure

   The tree has root 1, left child 2 with children 4 and 5, and right child 3.

2. Step 2: Find longest path between any two nodes

   Longest path is from node 4 to node 3 via 2 and 1: path 4->2->1->3 = 3 edges, diameter = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Count edges on longest path between two nodes [OK]

Common Mistakes:

• Counting nodes instead of edges or vice versa
• Ignoring paths not passing through root
• Miscounting edges in path

4. Identify the bug in this diameter calculation method and select the fix:

int diameter = 0;
int height(TreeNode root) {
  if (root == null) return 0;
  int left = height(root.left);
  int right = height(root.right);
  diameter = Math.max(diameter, left + right);
  return Math.max(left, right);
}

medium

A. Return Math.max(left, right) + 1 instead of Math.max(left, right)

B. Initialize diameter inside height method

C. Use diameter = Math.min(diameter, left + right)

D. Return left + right instead of Math.max(left, right)

Solution

1. Step 1: Understand height calculation

   Height of a node is 1 plus max height of its children, so must add +1.

2. Step 2: Identify bug in return statement

   Current code returns max(left, right) without +1, so height is underestimated.

3. Final Answer:

   Return Math.max(left, right) + 1 instead of Math.max(left, right) -> Option A

4. Quick Check:

   Height = max child height + 1 [OK]

Hint: Height adds 1 to max child height [OK]

Common Mistakes:

• Forgetting to add +1 in height return
• Using min instead of max for diameter update
• Returning sum of left and right as height

5. You want to find the diameter of a binary tree but also print the nodes on the longest path. Which approach is best?

hard

A. Modify the diameter function to store and return the longest path nodes along with diameter

B. Calculate diameter first, then do a separate BFS to find longest path nodes

C. Use only height function and print nodes at max height

D. Count leaf nodes and assume longest path is between two leaves

Solution

1. Step 1: Understand diameter and path relationship

   Diameter is longest path length; to print nodes, we must track path during diameter calculation.

2. Step 2: Choose approach that combines diameter and path tracking

   Modifying diameter function to store nodes on longest path is efficient and direct.

3. Final Answer:

   Modify the diameter function to store and return the longest path nodes along with diameter -> Option A

4. Quick Check:

   Track path during diameter calc for nodes [OK]

Hint: Track nodes while computing diameter for path [OK]

Common Mistakes:

• Running BFS separately wastes time
• Assuming height equals diameter path
• Counting leaves without path tracking