Binary Tree Diameter: Algorithm and Implementation Guide

Understanding the Binary Tree Diameter: Key Concepts and Code Guide

The diameter (or width) of a binary tree represents the longest path between any two nodes. This guide explains how to calculate it efficiently with examples and implementation.

Understanding Binary Tree Diameter

Definition

• The diameter is the longest path between any two nodes

• The path doesn't need to pass through the root

• Path length is measured by the number of edges between nodes

Key Concepts

1. The diameter at any node can be:

   • Path through the node (left height + right height)

   • Diameter of left subtree

   • Diameter of right subtree

Algorithm Implementation

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function diameterOfBinaryTree(root) {
    let maxDiameter = 0;
    
    function calculateHeight(node) {
        if (!node) return 0;
        
        // Calculate heights of left and right subtrees
        const leftHeight = calculateHeight(node.left);
        const rightHeight = calculateHeight(node.right);
        
        // Update maximum diameter if current path is longer
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
        
        // Return height of current node
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    calculateHeight(root);
    return maxDiameter;
}

Examples

Example 1: Simple Tree

     1
    / \
   2   3
  / \
 4   5

• Diameter = 3 (path: 4 → 2 → 1 → 3)

• Time to calculate: O(n)

• Space complexity: O(h) where h is height

Example 2: Linear Tree

  1
  /
 2
/
3

• Diameter = 2 (path: 3 → 2 → 1)

• Shows that diameter doesn't need to pass through root

Algorithm Analysis

Time Complexity

• O(n) where n is the number of nodes

• Each node is visited exactly once

Space Complexity

• O(h) where h is the height of the tree

• Due to recursion stack

Testing the Implementation

// Test cases
const tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);
tree1.left.left = new TreeNode(4);
tree1.left.right = new TreeNode(5);

console.log(diameterOfBinaryTree(tree1)); // Expected: 3

const tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);

console.log(diameterOfBinaryTree(tree2)); // Expected: 1

---