Diameter of Binary Tree in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of diameter calculation for a simple binary tree

What is the output of the following Java code that calculates the diameter of a binary tree?

DSA Java

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

public class Solution {
    int maxDiameter = 0;

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

    private int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        maxDiameter = Math.max(maxDiameter, left + right);
        return Math.max(left, right) + 1;
    }

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

A 2

B 5

C 4

D 3

💡 Hint

Think about the longest path between any two nodes in the tree.

The diameter is the longest path between any two nodes. Here, the longest path goes through nodes 4 -> 2 -> 1 -> 3, which has length 3 edges.

🧠 Conceptual

intermediate

Understanding diameter calculation logic

In the diameter calculation algorithm, what does the variable 'maxDiameter' represent during recursion?

A The total number of nodes in the tree

B The depth of the current node

C The maximum sum of depths of left and right subtrees found so far

D The height of the tree

💡 Hint

Consider what the diameter means in terms of subtree depths.

During recursion, 'maxDiameter' keeps track of the largest sum of left and right subtree depths found at any node, which corresponds to the longest path through that node.

🔧 Debug

advanced

Identify the error in diameter calculation code

What error will the following code produce when calculating the diameter of a binary tree?

DSA Java

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

public class Solution {
    int maxDiameter = 0;

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

    private int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        maxDiameter = Math.max(maxDiameter, left - right);
        return Math.max(left, right) + 1;
    }
}

A The diameter will be incorrect because it uses subtraction instead of addition

B NullPointerException at runtime

C StackOverflowError due to infinite recursion

D Compilation error due to missing return statement

💡 Hint

Check how maxDiameter is updated.

The code incorrectly uses subtraction (left - right) instead of addition (left + right) when updating maxDiameter, so the diameter value will be wrong.

❓ Predict Output

advanced

Output of diameter for a skewed binary tree

What is the output of the diameter calculation for the following skewed binary tree?

DSA Java

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

public class Solution {
    int maxDiameter = 0;

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

    private int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        maxDiameter = Math.max(maxDiameter, left + right);
        return Math.max(left, right) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.right.right.right = new TreeNode(4);
        Solution sol = new Solution();
        System.out.println(sol.diameterOfBinaryTree(root));
    }
}

A 4

B 3

C 1

D 0

💡 Hint

Consider the longest path in a skewed tree.

The longest path is along the right side from node 1 to node 4, which has 3 edges, so diameter is 3.

🧠 Conceptual

expert

Why does diameter calculation use post-order traversal?

Why is post-order traversal used in the diameter of binary tree algorithm?

A Because it ensures left and right subtree depths are calculated before updating diameter at the current node

B Because it visits nodes in ascending order of their values

C Because it only visits leaf nodes

D Because it uses less memory than pre-order traversal

💡 Hint

Think about when subtree information is needed to compute diameter at a node.

Post-order traversal visits left and right children before the current node, allowing the algorithm to know subtree depths before updating the diameter at the current node.

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