DSA Sheet by Technical Mickey

Diameter of Binary Tree

Problem Description

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. The path may or may not pass through the root.

The length of a path between two nodes is measured as the number of edges between them.

Intuition

The longest path between any two nodes in a binary tree is determined by its height properties. The key observations are:

The diameter of a node is the sum of the height of its left subtree and the height of its right subtree.
The diameter at each node is a candidate for the overall tree diameter.
A recursive approach can efficiently compute the height of each node while maintaining a global maximum for the diameter.

Solution Approach

To compute the diameter efficiently, we use a recursive depth-first search (DFS) approach with the following steps:

Define a recursive function to compute the height of a node.
At each node, calculate:
- The height of the left subtree.
- The height of the right subtree.
- The diameter at the current node as (leftHeight + rightHeight).
Update the global maximum diameter if the computed diameter at the current node is larger than the previously stored value.
Return the height of the current node as 1 + max(leftHeight, rightHeight).
The final result is the maximum recorded diameter during traversal.

This approach ensures we efficiently compute the diameter in O(N) time complexity, where N is the number of nodes.

Example Walkthrough

Example 1

Input:

Step-by-step Calculation:

The height of node 4 = 1, and node 5 = 1.
The height of node 2 = 1 + max(1, 1) = 2.
The height of node 3 = 1.
The diameter at node 2 = 1 (left) + 1 (right) = 2.
The diameter at node 1 = 2 (left) + 1 (right) = 3.

Output:

(Valid paths: [4 → 2 → 1 → 3] or [5 → 2 → 1 → 3])

Solution Implementation (Java)

				
					public class DiameterOfBinaryTree {
    static int maxDiameter = 0;

    public static int height(TreeNode root) {
        if (root == null) return 0;

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // Update the maximum diameter found
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

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

    public static int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        height(root);
        return maxDiameter;
    }

Time and Space Complexity Analysis

Time Complexity: O(N)

Each node is visited once during recursion.
The function height(root) performs O(1) operations per node, leading to an O(N) total runtime.

Space Complexity: O(H)

The recursive call stack grows up to the height of the tree (H).
In a balanced tree, H = log N, so space complexity is O(log N).
In a skewed tree, H = N, so worst-case space complexity is O(N).

Technical Mickey