Diameter of Binary Tree in DSA C - Deep Dive

Overview - Diameter of Binary Tree

What is it?

The diameter of a binary tree is the longest path between any two nodes in the tree. This path may or may not pass through the root. The diameter is measured by the number of edges on this longest path. It helps us understand the widest spread of the tree structure.

Why it matters

Knowing the diameter helps in understanding the maximum distance between nodes in a network or hierarchy, which is useful in optimizing communication or data flow. Without this concept, we might miss critical bottlenecks or longest routes in tree-like structures, leading to inefficient designs or slow operations.

Where it fits

Before learning this, you should understand binary trees and tree traversal techniques. After this, you can explore related tree problems like height, balanced trees, and path sums.

Mental Model

Core Idea

The diameter of a binary tree is the longest path between any two nodes, found by combining the longest paths through left and right subtrees at each node.

Think of it like...

Imagine a family tree where the diameter is the longest chain of relatives connected through parent-child links, showing the greatest distance between any two family members.

       (Node)
       /    \
  Left Subtree  Right Subtree
       \        /
        Longest path through node

Diameter = max(left height + right height) over all nodes

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. Each node stores a value and pointers to its children or NULL if none exist.

Result

You can represent and traverse a binary tree.

Understanding the basic structure is essential before measuring distances or paths within the tree.

2

Foundation

Height of a Binary Tree Node

Concept: Height is the longest path from a node down to a leaf.

Height of a node is 0 if it has no children. Otherwise, height = 1 + max(height of left child, height of right child).

Result

You can calculate how tall a subtree is from any node.

Height is a building block for finding the diameter since diameter depends on subtree heights.

3

Intermediate

Longest Path Through a Node

🤔Before reading on: Do you think the longest path always passes through the root? Commit to yes or no.

Concept: The longest path (diameter) may pass through any node, combining left and right subtree heights.

At each node, the longest path through it is left subtree height + right subtree height. We check this for every node to find the maximum.

Result

You can find candidate longest paths at each node.

Knowing the diameter can be anywhere prevents limiting the search to the root only.

4

Intermediate

Recursive Diameter Calculation

🤔Before reading on: Will calculating diameter require visiting every node? Commit to yes or no.

Concept: Use recursion to compute height and diameter simultaneously for each node.

Define a function that returns height and updates a global max diameter by checking left height + right height at each node.

Result

You can compute diameter in one tree traversal.

Combining height and diameter calculations saves time and avoids repeated work.

5

Advanced

Efficient Single-Pass Diameter Algorithm

🤔Before reading on: Do you think separate height and diameter traversals are efficient? Commit to yes or no.

Concept: Calculate diameter in one pass by updating max diameter during height calculation.

In the recursive function, compute left and right heights, update max diameter if left + right is larger, then return height = 1 + max(left, right).

Result

Diameter is found in O(n) time with one traversal.

Understanding this optimization is key for performance in large trees.

6

Expert

Handling Edge Cases and Tree Variants

🤔Before reading on: Does diameter change if the tree is skewed or empty? Commit to yes or no.

Concept: Consider empty trees, single-node trees, and skewed trees in diameter calculation.

Empty tree diameter is 0. Single node diameter is 0 (no edges). Skewed trees have diameter equal to height. Algorithm must handle these gracefully.

Result

Robust diameter calculation that works for all tree shapes.

Knowing edge cases prevents bugs and ensures correctness in all scenarios.

Under the Hood

The algorithm uses recursion to explore each node's left and right subtrees, calculating their heights. At each node, it sums these heights to find the longest path through that node. A global variable tracks the maximum sum found, which is the diameter. The recursion unwinds returning heights to parent calls, enabling a single traversal to compute diameter.

Why designed this way?

This approach avoids repeated height calculations by combining height and diameter computations in one pass, improving efficiency from O(n^2) to O(n). Early methods computed height separately for each node, causing slowdowns on large trees.

          ┌───────────────┐
          │   Current Node │
          ├───────────────┤
          │  /           \ │
          │Left Subtree  Right Subtree
          │  \           / │
          └───┬─────────┬─┘
              │         │
      Left Height  Right Height
              │         │
              └─────┬───┘
                    │
          Diameter Candidate = Left Height + Right Height
                    │
          Update Global Max Diameter if larger

Myth Busters - 3 Common Misconceptions

Quick: Does the diameter always pass through the root node? Commit to yes or no.

Common Belief: The diameter must pass through the root because it's the top of the tree.

Reality: The diameter can pass through any node, not necessarily the root.

Why it matters: Assuming it passes through the root can cause missing the true longest path, leading to incorrect diameter results.

Quick: Is the diameter the number of nodes on the longest path? Commit to yes or no.

Common Belief: Diameter counts nodes on the longest path between two nodes.

Reality: Diameter counts edges, which is one less than the number of nodes on the path.

Why it matters: Confusing nodes and edges leads to off-by-one errors in diameter calculation.

Quick: Can you find diameter without visiting all nodes? Commit to yes or no.

Common Belief: You can find diameter by checking only some nodes or just the root's height.

Reality: You must visit every node to ensure the longest path is found anywhere in the tree.

Why it matters: Skipping nodes risks missing longer paths, causing incorrect diameter.

Expert Zone

1

The diameter calculation can be adapted to weighted trees by summing edge weights instead of counting edges.

2

In balanced trees, diameter is often close to twice the height, but skewed trees have diameter equal to height, affecting performance assumptions.

3

Global variables used in recursion for diameter tracking must be carefully managed in concurrent or multi-threaded environments.

When NOT to use

For very large trees stored on disk or distributed systems, recursive diameter calculation may be inefficient or infeasible; iterative or parallel algorithms are preferred.

Production Patterns

Diameter calculation is used in network topology analysis, phylogenetic tree comparisons, and optimizing hierarchical data structures for minimal latency.

Connections

Tree Height

Diameter calculation builds directly on the concept of tree height.

Understanding height is essential because diameter uses subtree heights to find longest paths.

Graph Longest Path Problem

Diameter is a special case of longest path in trees, which are acyclic graphs.

Knowing diameter helps grasp longest path challenges in general graphs, which are harder to solve.

Network Latency Optimization

Diameter corresponds to maximum delay in network paths.

Understanding diameter aids in designing networks with minimal worst-case communication delays.

Common Pitfalls

#1 Calculating diameter by separately computing height for each node leads to repeated work.

Wrong approach:

int height(TreeNode* node) {
if (!node) return 0;
return 1 + max(height(node->left), height(node->right));
}

int diameter(TreeNode* root) {
if (!root) return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
int leftDiameter = diameter(root->left);
int rightDiameter = diameter(root->right);
return max(leftHeight + rightHeight, max(leftDiameter, rightDiameter));
}

Correct approach:

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

Root cause:

Not combining height and diameter calculations causes repeated height computations, leading to inefficient O(n^2) time.

#2 Counting nodes instead of edges for diameter causes off-by-one errors.

Wrong approach:

diameter = leftHeight + rightHeight + 1; // counts nodes

Correct approach:

diameter = leftHeight + rightHeight; // counts edges

Root cause:

Confusing path length definitions between nodes and edges.

#3 Assuming diameter passes through root node only.

Wrong approach:

int diameterOfBinaryTree(TreeNode* root) {
return height(root->left) + height(root->right);
}

Correct approach:

Use recursive traversal to check diameter at every node, not just root.

Root cause:

Misunderstanding that longest path can be anywhere in the tree.

Key Takeaways

Diameter of a binary tree is the longest path between any two nodes, measured in edges.

It can pass through any node, not necessarily the root, so all nodes must be checked.

Calculating diameter efficiently requires combining height and diameter computations in one traversal.

Edge cases like empty or skewed trees affect diameter values and must be handled carefully.

Understanding diameter helps in network design, tree analysis, and optimizing hierarchical structures.

Practice

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

easy

A. The total number of nodes in the tree

B. The height of the tree

C. The length of the longest path between any two 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 longest path from root to leaf, leaf count is number of leaves, total nodes is size. Diameter is distinct.

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path length [OK]

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

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of edges
• Assuming diameter always passes through root

2. Which of the following C function signatures is correct for a helper function that returns the height of a binary tree node for diameter calculation?

easy

A. int height(struct Node* root);

B. void height(struct Node root);

C. int height(Node root);

D. int height(struct Node root);

Solution

1. Step 1: Check parameter type for tree node

   In C, tree nodes are passed as pointers to struct Node, so parameter should be struct Node* root.

2. Step 2: Check return type and parameter correctness

   Height returns int, so return type int is correct. Passing pointer is correct, not struct by value.

3. Final Answer:

   int height(struct Node* root); -> Option A

4. Quick Check:

   Pointer parameter and int return type [OK]

Hint: Use pointer to struct Node for tree nodes in C [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Using void return type instead of int
• Missing struct keyword in parameter

3. What is the output of the following C code snippet that calculates the diameter of a binary tree?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

int height(struct Node* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int diameter(struct Node* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  int leftDiameter = diameter(root->left);
  int rightDiameter = diameter(root->right);
  int maxDiameter = leftHeight + rightHeight + 1;
  if (leftDiameter > maxDiameter) maxDiameter = leftDiameter;
  if (rightDiameter > maxDiameter) maxDiameter = rightDiameter;
  return maxDiameter;
}

int main() {
  struct Node n1 = {1, NULL, NULL};
  struct Node n2 = {2, NULL, NULL};
  struct Node n3 = {3, &n1, &n2};
  printf("%d", diameter(&n3));
  return 0;
}

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Analyze tree structure

   Root n3 has two children n1 and n2, both leaves. Height of left and right subtree is 1 each.

2. Step 2: Calculate diameter

   Diameter = max of (leftHeight + rightHeight + 1, leftDiameter, rightDiameter) = max(1+1+1, 1, 1) = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Diameter = 3 nodes in longest path [OK]

Hint: Diameter = max(leftHeight + rightHeight + 1, leftDiameter, rightDiameter) [OK]

Common Mistakes:

• Confusing diameter with height
• Forgetting to add 1 for root node in diameter
• Using height instead of diameter in comparisons

4. Identify the bug in this C function that attempts to compute the diameter of a binary tree:

int diameter(struct Node* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  int leftDiameter = diameter(root->left);
  int rightDiameter = diameter(root->right);
  int maxDiameter = leftHeight + rightHeight;
  if (leftDiameter > maxDiameter) maxDiameter = leftDiameter;
  if (rightDiameter > maxDiameter) maxDiameter = rightDiameter;
  return maxDiameter;
}

medium

A. height function is not called correctly

B. maxDiameter should be leftHeight + rightHeight + 1

C. Function should return height, not diameter

D. Missing base case for leaf nodes

Solution

1. Step 1: Check diameter calculation formula

   Diameter includes edges between nodes, so it should add 1 for the root node connecting left and right paths.

2. Step 2: Identify missing +1 in maxDiameter

   Current code misses +1, so maxDiameter undercounts by 1.

3. Final Answer:

   maxDiameter should be leftHeight + rightHeight + 1 -> Option B

4. Quick Check:

   Diameter = leftHeight + rightHeight + 1 [OK]

Hint: Add 1 to sum of heights for diameter at root [OK]

Common Mistakes:

• Omitting +1 in diameter calculation
• Confusing height and diameter returns
• Not handling null root base case

5. Given a binary tree where each node stores an integer, how would you modify the diameter calculation to find the diameter based on the sum of node values along the longest path instead of the number of nodes?

hard

A. Change height function to return max sum of node values from root to leaf, and update diameter to sum left and right max sums plus root's value

B. Use the existing diameter function but multiply the result by the root node's value

C. Replace all node values with 1 and then calculate diameter normally

D. Calculate diameter normally and then add all node values in the tree separately

Solution

1. Step 1: Modify height to return max sum path

   Instead of counting nodes, height returns max sum of node values from root to leaf recursively.

2. Step 2: Update diameter to sum left and right max sums plus root value

   Diameter becomes max of leftDiameter, rightDiameter, and leftSum + rightSum + root's value.

3. Final Answer:

   Change height function to return max sum of node values from root to leaf, and update diameter to sum left and right max sums plus root's value -> Option A

4. Quick Check:

   Diameter by sum = max path sum through root [OK]

Hint: Use max sum path instead of node count for diameter sum [OK]

Common Mistakes:

• Multiplying diameter by root value incorrectly
• Ignoring node values in diameter calculation
• Adding all node values separately instead of path sums