Posts Diameter of a Binary Tree (geeksforgeeks - SDE Sheet)
Post
Cancel

Diameter of a Binary Tree (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes.

geeksforgeeks

SOLUTION

The key idea is to compute the height of the left and right subtrees for each node and then sum these heights to get the path length passing through that node.

We maintain a global variable max that stores the maximum diameter encountered so far.

For each node, we calculate three values: the height of the left subtree plus one, the height of the right subtree plus one, and the combined left and right subtree path passing through the node. We update the maximum diameter using the largest of these values.

The important part is while returning the length. We should only consider either the nodes on left or right but not both. The combined part cannot be part of path for the parent node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {

    // Variable to store the maximum diameter found
    int max = 0;

    int diameter(Node root) {
        diameterHelper(root);
        return max;
    }

    int diameterHelper(Node root) {

        // Base case: if the node is null, return 0 (no height)
        if (root == null)
            return 0;

        // Recursively find the height of the left subtree
        int left = diameterHelper(root.left);

        // Recursively find the height of the right subtree
        int right = diameterHelper(root.right);

        // Calculate the combined length of the left and right path passing through the current node
        int combined = left + right + 1;

        // Update the maximum diameter encountered so far
        max = Math.max(max, Math.max(left + 1, Math.max(right + 1, combined)));

        // Return the height of the current subtree (which is the maximum height of either left or right plus 1)
        // We don't consider combined path here, since that cannot be used for the path in parent node
        return Math.max(left + 1, right + 1);
    }
}
This post is licensed under CC BY 4.0 by the author.