What is top-down recursion?
In a top-down traversal you push knowledge down the tree: each call receives the accumulated state of the path so far (a running sum, a max-so-far, the current depth) as a parameter. You update it, then hand the new value to your children.
Contrast with bottom-up, where children return values that the parent combines. Top-down answers questions like "count nodes whose path from the root satisfies X" or "is there a root-to-leaf path summing to target?" — the answer at a leaf depends only on what flowed down to it.
// top-down: state flows DOWN as a param
dfs(node, carry):
if node == null: return
carry = update(carry, node.val)
if isLeaf(node): check(carry)
dfs(node.left, carry)
dfs(node.right, carry)
dfs(node, carry):
if node == null: return
carry = update(carry, node.val)
if isLeaf(node): check(carry)
dfs(node.left, carry)
dfs(node.right, carry)
Time Complexity
O(N)
Each node is visited once; the carry update is O(1) per node.
Space Complexity
O(H)
Recursion stack depth equals the tree height H (O(N) if skewed).
Live Visualization
Current call
On active path
Contributes to answer
Returned
Call stack (top = current) — each frame carries state down
Answer accumulator
node = –
carry = 0
depth = 0
answer = 0
Step 0 / 0
Current node
–
being processed
Carry down
0
running sum
Depth
0
stack size
Answer
0
accumulated
Pick a mode and hit Play to watch state flow down the tree.
✓ Done
Speed
Step-by-step trace
| # | Action | Node | Carry in | Depth | Answer |
|---|
C++ — Path Sum (LC 112)