DP on Trees Diameter of Tree in DSA Typescript - Time & Space Complexity

Time Complexity: DP on Trees Diameter of Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to find the longest path in a tree using dynamic programming.

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function treeDiameter(adj: number[][]): number {
  let diameter = 0;
  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0;
    for (const child of adj[node]) {
      if (child === parent) continue;
      const length = dfs(child, node);
      if (length > max1) {
        max2 = max1;
        max1 = length;
      } else if (length > max2) {
        max2 = length;
      }
    }
    diameter = Math.max(diameter, max1 + max2);
    return max1 + 1;
  }
  dfs(0, -1);
  return diameter;
}
    

This code finds the longest path (diameter) in a tree using a depth-first search and dynamic programming.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive depth-first search (dfs) visits each node once.
• How many times: Each node and its edges are processed exactly once during the recursion.

How Execution Grows With Input

As the number of nodes grows, the function visits each node and edge once.

Input Size (n)	Approx. Operations
10	About 10 nodes and their edges visited once each
100	About 100 nodes and their edges visited once each
1000	About 1000 nodes and their edges visited once each

Pattern observation: The work grows roughly in direct proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the diameter grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The diameter calculation takes quadratic time because it checks all pairs of nodes."

[OK] Correct: The code uses a single depth-first search that visits each node once, avoiding repeated checks of node pairs.

Interview Connect

Understanding this linear time approach shows you can handle tree problems efficiently, a key skill in many coding challenges.

Self-Check

"What if the tree was represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"