Introduction & Problem Explanation

The Diameter of a Binary Tree is defined as the length of the longest path between any two nodes in a tree. The path does not necessarily have to pass through the root. The length of a path between two nodes is represented by the number of edges between them.

This problem is tricky because the longest path can reside completely in the left subtree, completely in the right subtree, or traverse across the root connecting nodes on both subtrees. To find the overall maximum diameter, we need to inspect the split-path potential of every single node in the tree.

Illustration of Diameter of Binary Tree using DFS height calculation in Java
Real-World Analogy: The Longest Highway Route

Imagine a highway network structured like a tree. Each town is a node, and the roads connecting them are branches. You want to find the longest driving route between any two dead-end towns (leaves) without backtracking.

For any specific town (node) acting as an intersection, the longest route that passes through it is the sum of the longest one-way road going down its left region (left depth) and the longest one-way road going down its right region (right depth). By checking every intersection town in the network, we find the absolute longest highway route!

The Algorithmic Approach

1. The Naive Approach - O(N²)

We can solve this by calculating the height of the left and right subtrees for every node in the tree, summing them, and keeping track of the maximum. Since calculating the height of a subtree takes O(N) time, repeating this for all N nodes leads to an inefficient quadratic time complexity of O(N²).

2. The Optimized DFS Approach - O(N)

Instead of doing redundant height calculations, we can combine the diameter calculation and height tracking into a single Depth-First Search (DFS) traversal. As we recursively calculate the height of each node (bottom-up post-order traversal):

  1. We fetch the maximum depth of the left subtree (left).
  2. We fetch the maximum depth of the right subtree (right).
  3. The diameter passing through the current node is left + right. We compare this with our global maximum diameter and update it if it's larger.
  4. We return the height of the current node to its parent, which is 1 + Math.max(left, right).

This post-order traversal visits each node exactly once, bringing the time complexity down to a highly optimized O(N).

Step-by-Step Execution Walkthrough

Let's trace the algorithm on the following binary tree:

          1
         / \
        2   3
       / \
      4   5
  1. Step 1: Start DFS traversal from the root (node 1). We must compute the height of its left child (node 2) and right child (node 3) first.
  2. Step 2: Traverse to node 2. To get its height, we traverse to its left child (node 4) and right child (node 5).
  3. Step 3: At leaf node 4: Both children are null, returning height 0. Local diameter = 0 + 0 = 0. Node 4 returns height 1 + max(0, 0) = 1 to node 2.
  4. Step 4: At leaf node 5: Both children are null, returning height 0. Local diameter = 0 + 0 = 0. Node 5 returns height 1 + max(0, 0) = 1 to node 2.
  5. Step 5: Back at node 2: Left child height = 1, right child height = 1. Local diameter = 1 + 1 = 2 (path 4 -> 2 -> 5). We update global max = 2. Node 2 returns height 1 + max(1, 1) = 2 to root (node 1).
  6. Step 6: At leaf node 3: Both children null, returns height 1 to root (node 1).
  7. Step 7: Back at root 1: Left child height = 2, right child height = 1. Local diameter = 2 + 1 = 3 (path 4 -> 2 -> 1 -> 3). We update global max = 3. Root returns height 3.
  8. Step 8: Traversal ends. The maximum diameter recorded is 3.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • if (node == null) return 0;: The base case for the recursive traversal. An empty subtree has a height of 0.
  • max = Math.max(max, left + right);: Updates our global variable max with the longest path found passing through the current node as the peak connector.
  • return 1 + Math.max(left, right);: Computes the height of the current node by taking the maximum path from either left or right child and adding 1 (representing the edge connecting the current node to its parent).

Complete Java Implementation

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class DiameterBinaryTree {

    public static class TreeNode {
        public int val;
        public TreeNode left, right;
        public TreeNode(int val) { this.val = val; }
    }

    int max = 0;
    
    // DFS + Height Tracking - O(n)
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode node) {
        if (node == null) return 0;
        int left = maxDepth(node.left);
        int right = maxDepth(node.right);
        max = Math.max(max, left + right);
        return 1 + Math.max(left, right);
    }

    public static void main(String[] args) {
        DiameterBinaryTree solver = new DiameterBinaryTree();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println("--- Diameter of Binary Tree Demonstration ---");
        System.out.println("Diameter: " + solver.diameterOfBinaryTree(root));
    }
}

Conclusion

Solving the Diameter of Binary Tree problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.