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

Time Complexity: Path Sum Root to Leaf in Binary Tree

O(n)

Understanding Time Complexity

We want to know how long it takes to check if a path from the root to any leaf adds up to a target sum in a binary tree.

How does the time needed grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }
    return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}
    

This code checks if there is any root-to-leaf path 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: Once per node in the tree, covering all paths.

How Execution Grows With Input

As the number of nodes grows, the function visits each node once, so the work grows proportionally.

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

Pattern observation: The operations grow 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 root-to-leaf paths by visiting every node, so it must check many nodes, not just one path.

Interview Connect

Understanding how recursive tree traversal scales helps you explain your solution clearly and shows you grasp how algorithms work on trees.

Self-Check

"What if the tree was balanced versus completely skewed? How would the time complexity change?"