Path Sum Root to Leaf in Binary Tree in DSA C++ - 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 grows as the tree gets bigger.

How does the number of nodes affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (!root->left && !root->right) 
        return targetSum == root->val;
    return hasPathSum(root->left, targetSum - root->val) ||
           hasPathSum(root->right, targetSum - root->val);
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

As the number of nodes grows, the function visits each node once to check paths.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to check paths grows linearly 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 root-to-leaf paths by visiting every node, so it must check many nodes, not just one path.

Interview Connect

Understanding this helps you explain how recursive tree traversal scales, a common skill in interviews.

Self-Check

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