Diameter of Binary Tree in DSA C

Mental Model

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

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

       1
      / \
     2   3
    / \
   4   5

Each number is a node. The diameter is the longest path between any two nodes.

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: max height of children + 1 = max(0,0)+1=1

Node 2 height = 1

Why: Height is longest path from node down to leaf

Step 4: Calculate height of node 3 (leaf)

Node 3 height = 0

Why: Leaf node height is 0

Step 5: Calculate diameter passing through node 2: left height + right height + 2 = 0 + 0 + 2 = 2

Diameter at node 2 = 2

Why: Longest path through node 2 includes edges to both children

Step 6: Calculate diameter passing through root node 1: left height + right height + 2 = 1 + 0 + 2 = 3

Diameter at node 1 = 3

Why: Longest path may pass through root combining left and right subtrees

Step 7: Compare diameters: max(2 at node 2, 3 at node 1) = 3

Final diameter = 3 edges

Why: Diameter is maximum of all subtree diameters

Result:

Diameter of the tree is 3 edges, path: 4 -> 2 -> 1 -> 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define the binary tree node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create a new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Helper function to find max of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Global variable to store the maximum diameter found
int maxDiameter = 0;

// Recursive function to find height of tree and update diameter
int height(Node* root) {
    if (root == NULL) {
        return -1; // height of empty tree is -1
    }
    int leftHeight = height(root->left); // height of left subtree
    int rightHeight = height(root->right); // height of right subtree

    // Calculate diameter passing through this node
    int diameterThroughRoot = leftHeight + rightHeight + 2;

    if (diameterThroughRoot > maxDiameter) {
        maxDiameter = diameterThroughRoot; // update max diameter
    }

    // Return height of this node
    return max(leftHeight, rightHeight) + 1;
}

// Function to get diameter of binary tree
int diameterOfBinaryTree(Node* root) {
    maxDiameter = 0; // reset global max diameter
    height(root); // compute heights and update diameter
    return maxDiameter;
}

int main() {
    // Build the tree from dry run example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    int diameter = diameterOfBinaryTree(root);
    printf("Diameter of the tree is %d\n", diameter);

    return 0;
}

int height(Node* root) {

start recursive height calculation

if (root == NULL) { return -1; }

base case: empty subtree height is -1

int leftHeight = height(root->left);

recursively find left subtree height

int rightHeight = height(root->right);

recursively find right subtree height

int diameterThroughRoot = leftHeight + rightHeight + 2;

calculate diameter passing through current node

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

update global max diameter if current is larger

return max(leftHeight, rightHeight) + 1;

return height of current node

Output

Diameter of the tree is 3

Complexity Analysis

Time: O(n) because we visit each node once to calculate height 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 calculates height and diameter in one pass

Edge Cases

Empty tree (root is NULL)

Diameter is 0 because there are no nodes

DSA C

if (root == NULL) { return -1; }

Single node tree

Diameter is 0 because no edges exist

DSA C

if (root == NULL) { return -1; }

Tree with only left or only right children

Diameter equals height of the longest path (number of edges)

DSA C

int diameterThroughRoot = leftHeight + rightHeight + 2;

When to Use This Pattern

When asked for the longest path between any two nodes in a tree, use the diameter pattern by combining heights of left and right subtrees at each node.

Common Mistakes

Mistake: Returning height as 0 for NULL nodes instead of -1, causing off-by-one errors in diameter calculation
Fix: Return -1 for NULL nodes so that height of leaf nodes is 0 and diameter counts edges correctly

Summary

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

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

The diameter is the largest sum of left and right subtree heights plus two edges at any node.

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