DP on Trees Maximum Path Sum in DSA Typescript - Time & Space Complexity

Time Complexity: DP on Trees Maximum Path Sum

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum path sum in a tree grows as the tree gets bigger.

Specifically, how does the number of steps change when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(dfs(node.left), 0);
    const right = Math.max(dfs(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}
    

This code finds the maximum sum of values along any path in a binary tree using a depth-first search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive depth-first search (dfs) visits each node once.
• How many times: Each node is visited exactly one time during the recursion.

How Execution Grows With Input

As the number of nodes in the tree increases, the number of recursive calls grows linearly.

Input Size (n)	Approx. Operations
10	About 10 recursive calls
100	About 100 recursive calls
1000	About 1000 recursive calls

Pattern observation: The number of steps grows directly in proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum path sum grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because the function calls itself twice per node, the time is O(2^n)."

[OK] Correct: Each node is visited only once because the recursion branches do not overlap; the calls form a tree structure with n nodes, so total calls are n, not exponential.

Interview Connect

Understanding this linear time complexity helps you explain how efficient tree algorithms work and shows you can analyze recursive solutions clearly.

Self-Check

"What if the tree was very unbalanced and looked like a linked list? How would the time complexity change?"