Diameter of Binary Tree in DSA C#

Mental Model

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

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

      1
     / \
    2   3
   / \    
  4   5   

Diameter is the longest path between two nodes, e.g., 4 -> 2 -> 1 -> 3

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)

4 -> null

Why: Leaf node height is 0, base case for recursion

Step 2: Calculate height of node 5 (leaf)

5 -> null

Why: Leaf node height is 0, base case for recursion

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

2 -> [4,5]

Why: Height is max height of children + 1; also update diameter as left height + right height + 2

Step 4: Calculate height of node 3 (leaf)

3 -> null

Why: Leaf node height is 0

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

1 -> [2,3]

Why: Update diameter if path through 1 is longer than current max

Result:

Diameter path length is 3 (edges) corresponding to path 4 -> 2 -> 1 -> 3

Annotated Code

DSA C#

using System;

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

public class Solution {
    private int maxDiameter = 0;

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

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

        int diameterThroughNode = leftHeight + rightHeight + 2; // edges count
        if (diameterThroughNode > maxDiameter) {
            maxDiameter = diameterThroughNode; // update max diameter if larger
        }

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

    public int DiameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        Height(root);
        return maxDiameter;
    }

    public static void Main() {
        TreeNode root = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)),
            new TreeNode(3));

        Solution sol = new Solution();
        int diameter = sol.DiameterOfBinaryTree(root);
        Console.WriteLine(diameter);
    }
}

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

return -1 for null to count edges correctly

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

recursively get left subtree height

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

recursively get right subtree height

int diameterThroughNode = leftHeight + rightHeight + 2; // edges count

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 calls

Output

3

Complexity Analysis

Time: O(n) because we visit each node once to calculate heights and update 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 uses post-order traversal to compute heights and diameter in one pass

Edge Cases

Empty tree (root is null)

Diameter is 0 because there are no nodes

DSA C#

if (node == null) return -1;

Single node tree

Diameter is 0 because no edges exist

DSA C#

if (node == null) return -1;

Tree with only left or only right children

Diameter equals height of the chain (number of edges)

DSA C#

int diameterThroughNode = leftHeight + rightHeight + 2;

When to Use This Pattern

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

Common Mistakes

Mistake: Returning 0 for null nodes instead of -1 causes off-by-one errors in edge counting.
Fix: Return -1 for null nodes so height counts edges correctly.

Mistake: Calculating diameter only through root misses longest path elsewhere.
Fix: Update diameter at every node considering paths through that node.

Summary

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

Use when you need the maximum distance between nodes, not just depth.

The diameter can pass through any node, so track max path during height calculation.

Practice

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

easy

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

B. The height of the tree from root to the deepest leaf

C. The total number of nodes in the tree

D. The number of leaf nodes in the tree

Solution

1. Step 1: Understand the diameter concept

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

2. Step 2: Differentiate from height and node count

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

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path between nodes [OK]

Hint: Diameter is longest path, not just height or node count [OK]

Common Mistakes:

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

2. Which of the following C# method signatures is correct for a function that calculates the diameter of a binary tree node?

easy

A. Diameter public int(TreeNode root)

B. int Diameter(TreeNode root) void

C. public void Diameter(TreeNode root) int

D. public int Diameter(TreeNode root)

Solution

1. Step 1: Review C# method signature syntax

   In C#, method signature starts with access modifier, return type, method name, and parameters in parentheses.

2. Step 2: Check each option

   public int Diameter(TreeNode root) follows correct syntax: public int Diameter(TreeNode root). Others have incorrect order or missing parts.

3. Final Answer:

   public int Diameter(TreeNode root) -> Option D

4. Quick Check:

   Correct C# method syntax = public int Diameter(TreeNode root) [OK]

Hint: Method signature: access modifier + return type + name + parameters [OK]

Common Mistakes:

• Placing return type after parameters
• Omitting access modifier or return type
• Incorrect order of keywords

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

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

// Tree structure:
//       1
//      / \
//     2   3
//    / 
//   4

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

int diameter = CalculateDiameter(root); // Assume CalculateDiameter correctly implemented
Console.WriteLine(diameter);

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Visualize the tree and longest path

   The longest path is from node 4 to node 3: path length = edges 4->2->1->3 = 3 edges.

2. Step 2: Calculate diameter as number of edges

   Diameter counts edges, so longest path length is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path edges = 3 [OK]

Hint: Count edges on longest path, not nodes [OK]

Common Mistakes:

• Counting nodes instead of edges
• Assuming diameter passes through root only
• Ignoring one side of the tree

4. Identify the bug in this C# code snippet for calculating the diameter of a binary tree:

int maxDiameter = 0;
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 + 1);
  return Math.Max(left, right) + 1;
}

int Diameter(TreeNode root) {
  Depth(root);
  return maxDiameter;
}

medium

A. The base case should return 1 instead of 0

B. Diameter should be maxDiameter - 1 because diameter counts edges, not nodes

C. maxDiameter should be reset inside Depth method

D. Depth method should return left + right instead of max

Solution

1. Step 1: Understand diameter counting edges vs nodes

   The code adds left + right + 1 (nodes), but diameter counts edges, so subtract 1.

2. Step 2: Fix return value in Diameter method

   Return maxDiameter - 1 to convert node count to edge count for diameter.

3. Final Answer:

   Diameter should be maxDiameter - 1 because diameter counts edges, not nodes -> Option B

4. Quick Check:

   Diameter edges = nodes - 1 [OK]

Hint: Diameter = nodes on path - 1 (edges) [OK]

Common Mistakes:

• Returning maxDiameter directly without subtracting 1
• Changing base case return value incorrectly
• Resetting maxDiameter inside recursive calls

5. You want to find the diameter of a binary tree but also return the path nodes forming that diameter. Which approach correctly extends the diameter calculation?

hard

A. Calculate diameter first, then do a separate BFS to find the path

B. Store all paths from root to leaves and pick the longest one

C. Modify the recursive function to return both depth and path, updating max path when diameter increases

D. Use a queue to traverse level by level and count nodes

Solution

1. Step 1: Understand diameter and path relationship

   Diameter is longest path between any two nodes, so tracking path during recursion helps capture it.

2. Step 2: Extend recursion to return depth and path

   Modify recursive calls to return depth and path list; update max path when a longer diameter is found.

3. Step 3: Compare other options

   Calculate diameter first, then do a separate BFS to find the path is inefficient; C only finds longest root-to-leaf path, not diameter; D is unrelated to diameter.

4. Final Answer:

   Modify the recursive function to return both depth and path, updating max path when diameter increases -> Option C

5. Quick Check:

   Track depth and path together for diameter path [OK]

Hint: Return depth and path in recursion to track diameter path [OK]

Common Mistakes:

• Trying to find path after diameter without tracking during recursion
• Confusing longest root-to-leaf path with diameter
• Using BFS level order traversal which doesn't find diameter