Course contentsShow
← Computer Science
Lesson 946 of 2,87222. Dynamic ProgrammingFree lesson

Tree Diameter via DP

Computing the longest path between any two nodes in a tree through dynamic programming.

Tree Diameter via DP

You'll learn how to compute the longest path between any two nodes in a tree using dynamic programming on subtrees.


The Core Idea

The diameter of a tree is the longest path between any two nodes, measured in number of edges. While you could check all pairs of nodes (expensive!), dynamic programming lets you solve this in a single tree traversal.

The key insight: the longest path in a tree either:

  1. Passes through the current node (connecting two subtrees), or
  2. Lies entirely within one of its subtrees.

For each node, compute two values:

  • Height: longest path going down from that node
  • Diameter candidate: longest path through that node (sum of two largest subtree heights)

Track the maximum diameter seen across all nodes as you go.


How It Works

Start from the leaves and work upward (post-order):

  1. Base case: A leaf has height 0, diameter 0
  2. Recursive step: For each node:
    • Get heights of all children's subtrees
    • Node's height = 1 + max(children's heights)
    • Path through this node = sum of two largest children's heights + 2
    • Update global diameter if this path is longer

This leverages subtree independence—each subtree's diameter is computed once and reused.


Why DP?

Without DP, you'd redundantly recompute paths. DP captures the optimal solution (longest path down) from each subtree, avoiding repeated work. This transforms an exponential problem into O(n) time.

Key Takeaway: Tree diameter is found by computing the maximum of all "paths through node X" values, where each uses DP-computed heights from subtrees below—leveraging overlapping subproblems and optimal substructure.