Grad shape
Grad shape

How To Keep Track of Traversed Path in DFS Tree and Graph Traversal

Get started
hero image
    🙏

    জয়  শ্রী  রাম

    🕉





Often times in Tree and Graph Traversal problems and Dynamic problems we face challenges in printing the optimal path(s) that led us to the answer. In this post we will demystify a robust way to print optimal paths for Binary Trees in a way that we can use this learning in solving various other problems where we are interested in knowing what are the paths that led us to a specific answer.

Our focus will be on the iterative approach here.

Let’s take a simple example.


Problem Statement: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
      9
     / \
    10  11
   /   / 
  2  6
 /  \      
7    5   
sum = 26
Return true, because there is a path 9 -> 10 -> 2 -> 5 from root to leaf which sums up to 26.

Solution: The solution for the above problem is quite simple and easy. We can solve them in several ways but I am showing two easy ways of solving below:

Solution#1. Iterative Preorder:


    public boolean hasRootToLeafPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Stack<Integer> sumStack = new Stack<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        sumStack.push(root.val);
        while (!stack.isEmpty()) {
            TreeNode currNode = stack.pop();
            int currSum = sumStack.pop();
            if (currNode.left == null && currNode.right == null && currSum == sum) {
                return true;
            }

            if (currNode.left != null) {
                stack.push(currNode.left);
                sumStack.push(currSum + currNode.left.val);
            }

            if (currNode.right != null) {
                stack.push(currNode.right);
                sumStack.push(currSum + currNode.right.val);
            }
        }
        return false;
    }

Approach#2. Iterative Inorder


       public boolean hasRootToLeafPathSum(TreeNode root, int target) {
        if (root == null) {
            return false;
        }
        Stack<Integer> sumStack = new Stack<>();
        Stack<TreeNode> stack = new Stack<>();
        int sum = 0;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                tempSum += root.val;
                sumStack.push(tempSum);
                root = root.left;
            }

            root = stack.pop();
            int currSum = sumStack.pop();
            if (root.left == null && root.right == null && currSum == target) {
                return true;
            }

            root = root.right;
            tempSum = currSum;
        }
        return false;
    }
}
    


Tracking Traversed Path:



Now let’s see how we can return the path that gave us the target sum. Basically what we will have to do is kind of State Management at Node level. By ‘state’ I mean the state of the path which led us to the current node. At every node we visit, we store and keep track of the path traversed. So say in a tree if I am now at NodeA, I will store the full path traversed till now including NodeA. And it will be true for every node we visit. Since we know the path till NodeA, if we visit the left child of NodeA, say NodeB, we just retrieve the path traversed till NodeA and add its left child to it, and voila! we got the path traversed till NodeB. For iterative approach this means we would need a stack just to store the full path traversed so far including the current node we are at. Let’s see how we can achieve that by extending the above code. Keep an eye on the line of code marked with "---->", added to track the path.


Iterative Preorder:



Login to Access Content



Inorder Traversal:



Login to Access Content



So what I tried to show here is tracking path that led to the optimal result is not as challenging as we think they are. The above approach can be extended to print all paths that lead to some desired result as well. For example, if we had to print all paths that sum up to a given target sum, we can use the same approach to return all the paths.

Recursive Approach

Now let’s see how we can keep track of paths in a recursive way.
The recursive algorithm for the above problem would be as follows.


Login to Access Content



The code is self-explanatory. If we reach a leaf and the target sum is not yet reached the leaf node returns an empty path, and backtracks to its parent. But what is most important is before backtracking it removes itself from the path since it is not part of a desired path, and this part is true for any node. Any node not part of the path we are looking for should remove itself before backtracking back to its parent. This is how we are keeping the path updated all the time.
And when we have found a desired path either from leftchild or rightchild, we return without removing itself from the path, because it is part of a desired path and needs to remain there. Now go through the code once more and try to grab the concept. You should be able to use this approach for Tree and Graph traversal in most cases where you need to return one or more desired path(s).
Now let’s see how we can extend this approach to return all desired paths instead of just one.

Problem #2.

Problem Statement: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
      9
     / \
    10  11
   /   / 
  2  6
 /  \      
7    5 
sum = 26

Solution:

A recursive solution for this problem would be as follows:


Login to Access Content




Look at the code carefully to see how similar it is to the recursive implementation for the Problem #1 and yet we were able to leverage and extend the code to print all desired paths in Problem #2. The iterative approach will be equally easy and we would be able to extend the iterative solution for Problem #1.




Iterative Preorder Solution:



Login to Access Content


Iterative Inorder Solution:



Login to Access Content


So if I have to come up with a simple strategy about how to keep track of path or anything else in a tree or graph, in most most of the cases having a stack for that should work. If you have notice we push or pop from the all the stacks (stack to keep the nodes, as well as stacks to keep track of anything we are interested in tracking at the node level) at the same time. That way if we pop from all these stacks at the same time we will get the attributes (which in our case is sum and path) related to the node at the top of the node stack. For example, in the Problem #1, we have 3 stacks: node stack, sum stack and path stack. At any point of time the size of these stacks will be the same, according to the above implementation. And at each level in any of the stacks the elements are tied to the node stored at that same level in node stack. If we pop from node stack, sum stack and path stack at the same time, we will get sum up to the node being popped, and the path traversed from root to get to this node which is being popped. The i-th element in path stack will be the path traversed from root to the i-th node in the node stack, and i-th element in the sum stack will be the sum up to the i-th node in the node stack from the root. This is how everything ties up here.
Just make sure to push and pop all of the stacks at the same time.

Put in one sentence, we track path for each node, and for each node we pass the information to their child nodes.



One last thought: The iterative approach to track paths is very inefficient when it comes to space complexity.
When space is a concern and depending on the nature of the input, recursive approach may often be a better solution in the context discussed in this article.


Instructor: