Tree Algorithms

Tree Diameter

What is the Diameter of a Tree?

The diameter of a tree is the number of edges on the longest path between any two nodes. That path doesn't have to pass through the root — it can start and end anywhere, and in most trees it actually cuts through some node in the middle where two deep subtrees meet.

How Does It Work?

The key insight: for any single node, the longest path that passes *through* it is the height of its left subtree plus the height of its right subtree — one leg going down each side. Checking every node this way and keeping the largest total automatically finds the true diameter, because whichever node happens to be the meeting point of the two longest branches will produce the biggest sum.

This means diameter can be computed in a single post-order traversal: recursively find the height of the left and right subtrees first, use them to compute this node's own height (1 + the taller side) and its "path-through" value (left height + right height), then update a running maximum. No repeated re-traversal is needed — every node's height is computed exactly once and reused by its parent.

Diameter = 4 edges — the path 1 → 3 → 8 → 10 → 14 turns at node 3
83101614
Path endpointsTurning point

Algorithm Steps

  1. Run a post-order traversal — process both children before the current node
  2. At each node, using the already-computed heights of its children:
    • This node's height = 1 + max(left child height, right child height)
    • The longest path through this node = left child height + right child height
  3. Track the maximum path-through value seen across every node — that maximum is the diameter

Time Complexity

  • Time Complexity: O(n) — every node's height is computed exactly once in a single traversal.
  • Space Complexity: O(h) — recursion stack depth equals the tree's height (O(log n) balanced, O(n) skewed).

Time Complexity Analysis

Advertisement

Diameter shows up whenever "the two most distant points in a hierarchy" matters: the worst-case latency between two nodes in a network topology tree, the longest chain of dependencies in a build graph, or simply describing how "spread out" or "stringy" versus "bushy" a tree's shape is.

Daily DSA Challenge by Scale Engineer

Find the longest path between any two nodes in the tree

Tree is empty
No tree yet — insert a value or generate a random tree
Internal nodeLeaf nodeRootDiameter pathPath endpointsTurning point

Test Your Knowledge before moving forward!

Tree Diameter Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Tree Diameter Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Single post-order pass: each node's height is computed once and reused
// by its parent, while a running maximum tracks the widest "path-through" value.
function diameterOfTree(root) {
  let diameter = 0;

  function height(node) {
    if (node === null) return 0;

    const leftHeight = height(node.left);
    const rightHeight = height(node.right);

    // Longest path that turns at this node
    diameter = Math.max(diameter, leftHeight + rightHeight);

    // Height contributed upward to this node's parent
    return 1 + Math.max(leftHeight, rightHeight);
  }

  height(root);
  return diameter; // number of edges
}

// Usage example
let root = null;
[8, 3, 10, 1, 6, 14].forEach((v) => {
  root = insert(root, v); // see BST Insertion for insert
});

diameterOfTree(root); // 4

Done With the Learning

Mark Tree Diameter as done and view it on your dashboard

Explore Other Tree Topics

Lowest Common Ancestor

Tree Isomorphism

Serialize/Deserialize

BST Insertion

AVL Balancing

In-order Traversal

Structure & Properties