Diameter of Binary Tree

Find the diameter (longest path) of a binary tree.

Language Selection

Choose your preferred programming language

Showing: Python

Diameter of Binary Tree

Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Examples

Example 1:

Input: root = [1,2,3,4,5]
Output: 3

Explanation:
    1
   / \
  2   3
 / \
4   5

The longest path is [4,2,1,3] or [5,2,1,3] with length 3.

Example 2:

Input: root = [1,2]
Output: 1

Explanation:
  1
 /
2

The longest path is [2,1] with length 1.

Constraints

  • 1 <= Number of nodes <= 10^4
  • -100 <= Node.val <= 100

Approach 1: DFS with Global Maximum (Optimal)

Algorithm

Use DFS to calculate the height of each node and update the global maximum diameter.

Steps:

  1. For each node, calculate the height of left and right subtrees
  2. Update the diameter as the sum of left and right heights
  3. Return the height of current node (1 + max(left_height, right_height))
  4. Keep track of the maximum diameter found

Implementation

Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameterOfBinaryTree(root):
    """
    Find diameter of binary tree using DFS
    Time: O(n)
    Space: O(h) where h is height of tree
    """
    max_diameter = [0]  # Use list to allow modification in nested function
    
    def dfs(node):
        if not node:
            return 0
        
        # Get heights of left and right subtrees
        left_height = dfs(node.left)
        right_height = dfs(node.right)
        
        # Update diameter (path through current node)
        current_diameter = left_height + right_height
        max_diameter[0] = max(max_diameter[0], current_diameter)
        
        # Return height of current node
        return 1 + max(left_height, right_height)
    
    dfs(root)
    return max_diameter[0]

Java:

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

class Solution {
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        dfs(root);
        return maxDiameter;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // Get heights of left and right subtrees
        int leftHeight = dfs(node.left);
        int rightHeight = dfs(node.right);
        
        // Update diameter (path through current node)
        int currentDiameter = leftHeight + rightHeight;
        maxDiameter = Math.max(maxDiameter, currentDiameter);
        
        // Return height of current node
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Go:

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0
    
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        
        // Get heights of left and right subtrees
        leftHeight := dfs(node.Left)
        rightHeight := dfs(node.Right)
        
        // Update diameter (path through current node)
        currentDiameter := leftHeight + rightHeight
        if currentDiameter > maxDiameter {
            maxDiameter = currentDiameter
        }
        
        // Return height of current node
        if leftHeight > rightHeight {
            return leftHeight + 1
        }
        return rightHeight + 1
    }
    
    dfs(root)
    return maxDiameter
}

JavaScript:

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

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

C#:

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

public class Solution {
    private int maxDiameter = 0;
    
    public int DiameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        Dfs(root);
        return maxDiameter;
    }
    
    private int Dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // Get heights of left and right subtrees
        int leftHeight = Dfs(node.left);
        int rightHeight = Dfs(node.right);
        
        // Update diameter (path through current node)
        int currentDiameter = leftHeight + rightHeight;
        maxDiameter = Math.Max(maxDiameter, currentDiameter);
        
        // Return height of current node
        return 1 + Math.Max(leftHeight, rightHeight);
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node once
  • Space Complexity: O(h) - Recursion stack depth

Key Insights

  1. Diameter Definition: Longest path between any two nodes (may not pass through root)
  2. Height Calculation: For each node, diameter = left_height + right_height
  3. Global Maximum: Keep track of maximum diameter found during traversal
  4. Single Pass: Can find diameter in one DFS traversal
  5. Edge Count: Return number of edges, not nodes

Edge Cases

  1. Empty Tree: Return 0
  2. Single Node: Return 0 (no edges)
  3. Two Nodes: Return 1 (one edge)
  4. Left Skewed: Diameter equals number of nodes - 1
  5. Right Skewed: Diameter equals number of nodes - 1

Follow-up Questions

  1. Path Details: Return the actual path, not just the length?
  2. Multiple Diameters: Find all paths with maximum length?
  3. Weighted Edges: Handle trees with weighted edges?
  4. Diameter Updates: Handle dynamic tree modifications?
  5. Validation: Verify if a given path is the diameter?

Common Mistakes

  1. Node vs Edge Count: Confusing nodes with edges in diameter calculation
  2. Root Assumption: Assuming diameter always passes through root
  3. Global Variable: Not properly handling global maximum tracking
  4. Base Case: Not handling empty tree or single node cases
  5. Height Calculation: Incorrect height calculation for diameter

Interview Tips

  1. Clarify Requirements: Ask about edge vs node count and root assumption
  2. Discuss Approaches: Mention both single-pass and two-pass approaches
  3. Handle Edge Cases: Discuss empty tree, single node scenarios
  4. Explain Algorithm: Walk through the height calculation and diameter update
  5. Consider Optimizations: Discuss space-time tradeoffs