Binary Tree Diameter

Tags

Binary Tree Diameter

Category

Binary Trees

Difficulty

Medium

Problem Statement

Given a binary tree, find its diameter. The diameter of a binary tree is defined as the length of the longest path between any two nodes. This path may or may not pass through the root. The length of a path is measured by the number of edges between nodes.

Intuition

The longest path through any node is the sum of the heights of its left and right subtrees. The diameter is the maximum of this value across all nodes. By computing the height of each subtree recursively and tracking the maximum left-height + right-height seen so far, we can find the diameter in a single traversal.

Approach

  1. Define a recursive function that returns the height of the subtree rooted at the current node.
  2. For each node: a. Recursively compute the height of the left subtree. b. Recursively compute the height of the right subtree. c. The path through this node has length = leftHeight + rightHeight. d. Update the global maximum diameter if this path is longer. e. Return the height of this node: 1 + max(leftHeight, rightHeight).
  3. The base case: a null node has height 0.
  4. After traversal, return the maximum diameter found.

Pseudocode

function binaryTreeDiameter(root):
    maxDiameter = 0

    function getHeight(node):
        if node is null:
            return 0
        leftHeight = getHeight(node.left)
        rightHeight = getHeight(node.right)
        pathLength = leftHeight + rightHeight
        maxDiameter = max(maxDiameter, pathLength)
        return 1 + max(leftHeight, rightHeight)

    getHeight(root)
    return maxDiameter

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Every node is visited exactly once.
  • Space: O(h) where h is the height of the tree, due to the recursion stack. In the worst case (skewed tree), this is O(n). For a balanced tree, it is O(log n).

Key Insights

  • The diameter does not necessarily pass through the root. It could be entirely within a subtree.
  • By combining height computation with diameter tracking, we solve the problem in a single DFS pass.
  • The diameter through any node = leftHeight + rightHeight. The overall diameter is the maximum across all nodes.
  • Height and diameter are computed bottom-up, which is a natural fit for post-order traversal.

Edge Cases

  • Single node (no children): diameter is 0 (no edges).
  • Null/empty tree: diameter is 0.
  • Perfectly balanced tree: diameter passes through the root and equals 2 * height.
  • Completely skewed tree (linked list shape): diameter equals n - 1.
  • Tree where the longest path is entirely in one subtree and does not pass through the root.

Linked mentions