JOIN for daily coding insights

DSA Series Chapter 24 – DIAMETER OF BINARY TREE(C Version)

1. Objective

To compute the diameter of a binary tree using a recursive approach in C.

2. Definition (Exam-Ready)

The diameter of a binary tree is the number of nodes on the longest path between any two leaf nodes in the tree.

* The path may or may not pass through the root.

3. Example Binary Tree

Longest Path

4 → 2 → 1 → 3

Diameter

Nodes in path = 4
Diameter = 4

4. Important Observation

For every node:

Longest path through that node =
height(left subtree) + height(right subtree) + 1

The maximum such value over all nodes is the diameter.

5. Core Logic

Compute height of left subtree
Compute height of right subtree
Diameter at current node = lh + rh + 1
Recursively compute diameter of left subtree
Recursively compute diameter of right subtree
Return the maximum of all three

6. Recursive Formula

diameter(node) =
    max(
        height(left) + height(right) + 1,
        diameter(left),
        diameter(right)
    )

7. Structure Definition

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

8. Function to Find Height

int height(struct Node* root) {
    if (root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    return (lh > rh ? lh : rh) + 1;
}

9. Function to Find Diameter

int diameter(struct Node* root) {
    if (root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    int currentDiameter = lh + rh + 1;

    int leftDiameter = diameter(root->left);
    int rightDiameter = diameter(root->right);

    return (currentDiameter > leftDiameter ?
           (currentDiameter > rightDiameter ? currentDiameter : rightDiameter)
           : (leftDiameter > rightDiameter ? leftDiameter : rightDiameter));
}

10. Line-by-Line Explanation (Key Parts)

Height Function

Calculates maximum depth of subtree
Used to compute longest path through a node

Diameter Function

lh + rh + 1 → diameter through current node
Recursively checks left and right subtree diameters
Returns the maximum value

11. Complete C Program

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int height(struct Node* root) {
    if (root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    return (lh > rh ? lh : rh) + 1;
}

int diameter(struct Node* root) {
    if (root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    int currentDiameter = lh + rh + 1;

    int leftDiameter = diameter(root->left);
    int rightDiameter = diameter(root->right);

    if (currentDiameter > leftDiameter && currentDiameter > rightDiameter)
        return currentDiameter;
    else if (leftDiameter > rightDiameter)
        return leftDiameter;
    else
        return rightDiameter;
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Diameter of the binary tree: %d", diameter(root));
    return 0;
}