🙏

জয়  শ্রী  রাম

🕉

---

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

Iterative Preorder Solution:

Login to Access Content

Iterative Inorder Solution:

Login to Access Content

Instructor: