Iterative DFS for Root-to-Leaf Sum Paths

Welcome back! In our last lesson, we successfully adapted the iterative inorder traversal to validate a Binary Search Tree, highlighting how a specific traversal order can unlock an elegant solution. We saw how adding a prev pointer to our iterative template was the key modification.

Today, we'll continue exploring the power of adapting iterative DFS templates. We'll tackle another fundamental tree problem: finding all root-to-leaf paths that sum up to a given target. This will require a different traversal order and a more complex state management system than our BST validator, pushing you to think more deeply about what information you need to carry during a traversal.

By the end of this lesson, you will be able to implement an iterative DFS solution to find all root-to-leaf paths that match a target sum, a common pattern that reinforces your skills in stack-based traversal and state management.

Deconstructing the "Path Sum" Problem

First, let's precisely define the problem. We are given the root of a binary tree and a targetSum. Our task is to find all paths that start at the root and end at a leaf node, where the sum of the values of the nodes along the path equals the targetSum.

As the problem statement clarifies, a "path" is a sequence of nodes from the root down to a leaf (a node with no children). The core of the problem is a search. We need to explore every possible root-to-leaf path, calculate its sum, and if it matches the target, add it to our results.

This search process is naturally a Depth-First Search (DFS), as we explore one path to its conclusion (a leaf) before backtracking to explore another. The image below visualizes this process. The tree on the right shows the exploration, where each edge is labeled with the value of the child node, and the numbers next to the edges represent the remaining sum needed.

Why Preorder Traversal is the Right Tool

In our last lesson, the inorder traversal (Left -> Root -> Right) was perfect for BST validation because it visits nodes in sorted order. For building a root-to-leaf path, does inorder make sense?

Consider a path 5 -> 4 -> 11. To build this path, we must process 5, then 4, then 11. This Root -> Left -> Right processing order is the definition of preorder traversal.

When we visit a node in preorder, we can immediately add it to our current path and update our running sum. This top-down construction is intuitive and aligns perfectly with the problem. In contrast, inorder and postorder would process child nodes before their parents, making it difficult to construct the path from the root downwards.

The Iterative DFS Strategy: Using Parallel Stacks

Now that we've chosen our traversal strategy (preorder), how do we implement it iteratively to find these paths? A simple iterative preorder traversal using one stack only tells us the order of nodes. It doesn't inherently keep track of the path taken to reach each node or the sum of that path.

To solve this, we can extend our iterative DFS template by using parallel stacks to maintain the necessary state for each node in our traversal:

1. A node_stack: This is our primary stack for managing the DFS traversal, holding TreeNode objects.
2. A path_stack: This stack holds the list of node values representing the path from the root to the corresponding node in node_stack.
3. A sum_stack: This stack holds the integer sum of the corresponding path in path_stack.

These three stacks must always be kept in sync. When we pop a node from node_stack, we also pop its corresponding path and sum from the other two stacks. When we push a child node, we also construct and push its new path and updated sum.

This pattern is a powerful way to handle iterative tree problems where you need to reconstruct the path taken.

Implementation and Walkthrough

Let's examine a concrete implementation of this multi-stack strategy. The following article provides a clean Java solution. Note that this implementation calculates the remaining sum (targetSum - current_sum) and stores that, checking for 0 at the leaf. This is a common and efficient variation.

Let's trace this logic with the main example: targetSum = 22.

Initial State:

• nodeStack: [Node(5)]
• sumStack: [17] (22 - 5)
• pathStack: [[5]]
• result: []

Loop 1:

• pop Node(5), currentSum=17, currentPath=[5].
• It's not a leaf.
• push right child Node(8):
  • nodeStack: [Node(8)]
  • sumStack: [9] (17 - 8)
  • pathStack: [[5, 8]]
• push left child Node(4):
  • nodeStack: [Node(8), Node(4)]
  • sumStack: [9, 13] (17 - 4)
  • pathStack: [[5, 8], [5, 4]]

Loop 2:

• pop Node(4), currentSum=13, currentPath=[5, 4].
• Not a leaf. Has one child Node(11).
• push left child Node(11):
  • nodeStack: [Node(8), Node(11)]
  • sumStack: [9, 2] (13 - 11)
  • pathStack: [[5, 8], [5, 4, 11]]

Loop 3:

• pop Node(11), currentSum=2, currentPath=[5, 4, 11].
• Not a leaf.
• push right child Node(2):
  • nodeStack: [Node(8), Node(2)]
  • sumStack: [9, 0] (2 - 2)
  • pathStack: [[5, 8], [5, 4, 11, 2]]
• push left child Node(7):
  • nodeStack: [Node(8), Node(2), Node(7)]
  • sumStack: [9, 0, -5] (2 - 7)
  • pathStack: [[5, 8], [5, 4, 11, 2], [5, 4, 11, 7]]

Loop 4:

• pop Node(7), currentSum=-5, currentPath=[5, 4, 11, 7].
• It is a leaf node (left and right are null).
• Is currentSum == 0? No, it's -5. Do nothing.

Loop 5:

• pop Node(2), currentSum=0, currentPath=[5, 4, 11, 2].
• It is a leaf node.
• Is currentSum == 0? Yes! Found a path.
• Add a copy of currentPath to result. result is now [[5, 4, 11, 2]].

The process continues until the stacks are empty, at which point the second valid path [5, 8, 4, 5] will also have been found. The following video provides an excellent visual walkthrough of this same logic, which can help solidify the push/pop mechanics.

Complexity and A Crucial Trade-off

A key part of a deep understanding is analyzing the efficiency of our chosen algorithm. This is where the path-copying aspect of our iterative solution has important consequences.

• Time Complexity: We visit each of the $N$ nodes once. However, at each step when we process a node with children, we create a new copy of the current path to extend it. The path length can be up to the height of the tree, $H$. Therefore, the time complexity is $O(N\cdot H)$. For a balanced tree where $H\approx \log N$, this is $O(N\log N)$. But for a skewed, list-like tree where $H\approx N$, the complexity degrades to $O(N^2)$.

• Space Complexity: The space is dominated by the pathStack. In the worst case of a skewed tree, the stack depth is $H\approx N$. Each entry in the pathStack is a list of size up to $H$. This results in a space complexity of $O(H^2)$, which becomes $O(N^2)$ for a skewed tree.

This is a critical insight. While our multi-stack approach is robust and avoids recursion limits, it pays a price in time and space due to path copying. More advanced iterative solutions can simulate recursive backtracking with a single path list to achieve $O(H)$ space, but they are significantly more complex to implement correctly. For most interview settings, demonstrating this $O(N\cdot H)$ solution and being able to clearly articulate its complexity trade-offs is a strong signal of competence.

Conclusion

In this lesson, you've added another powerful pattern to your tree traversal toolkit. You learned how to adapt the iterative DFS framework to solve a path-finding problem by using parallel stacks to maintain state.

Key Takeaways:

• Root-to-leaf path problems are a natural fit for preorder traversal because it builds paths from the top down.
• An iterative solution can be implemented using parallel stacks to track the node, the path to that node, and the path's sum.
• This multi-stack approach involves a trade-off: it is conceptually more straightforward than simulating backtracking but has a time complexity of $O(N\cdot H)$ and space complexity of $O(H^2)$ due to path copying at each step.

We have now spent considerable time on adapting traversal algorithms. In our next lesson, we will shift gears and introduce a new data structure, the Heap, also known as a Priority Queue. We'll move from problems about visiting all nodes to problems about efficiently finding the "best" or k-th largest element, opening up a new category of algorithmic solutions.