Path Sum Root to Leaf in Binary Tree in DSA Javascript - Time & Space Complexity

Time Complexity: Path Sum Root to Leaf in Binary Tree

O(n)

Understanding Time Complexity

We want to know how the time needed to check if a path sum exists in a binary tree grows as the tree gets bigger.

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 hasPathSum(node, targetSum) {
  if (!node) return false;
  if (!node.left && !node.right) return targetSum === node.val;
  return hasPathSum(node.left, targetSum - node.val) || hasPathSum(node.right, targetSum - node.val);
}
    

This code checks if there is a root-to-leaf path in a binary tree where the sum of node values equals the target sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Each node is visited once in the worst case.

How Execution Grows With Input

As the number of nodes grows, the function checks each node once, so the steps grow roughly the same as the number of nodes.

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

Pattern observation: The work grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the path sum grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The function only checks one path, so it runs in constant time."

[OK] Correct: The function explores all possible root-to-leaf paths, so it must visit many nodes, not just one path.

Interview Connect

Understanding this helps you explain how recursive tree problems scale, a common skill interviewers look for.

Self-Check

"What if the tree is balanced vs completely skewed? How would the time complexity change?"