Java Recursive and Iterative (using 2 stacks) Solutions with explanation


  • 0

    Recursive Solution is intuitive and self - explanatory.

    public class Solution {
            public boolean hasPathSum(TreeNode node, int sum) {
    
                if(node == null)
                     return false;
                else if(sum-node.val == 0 && node.left == null && node.right == null)
                     return true;
                     
                     
                return hasPathSum(node.left,sum-node.val) || hasPathSum(node.right,sum-node.val);
            }
        }
    

    Iterative Solution -

    public class Solution {
    	
    	public boolean isParent(TreeNode possible_parent,TreeNode possible_child)
        {
            return possible_parent.left == possible_child || possible_parent.right == possible_child;
        }
    
        public boolean hasPathSum(TreeNode root, int sum) {
            if(root == null)
            return false;
            
                Stack<TreeNode> nodes = new Stack<TreeNode>();
                Stack<Integer> path_sum = new Stack<Integer>();
                
                // push initial values to both stacks 
    
                nodes.push(root);
                path_sum.push(root.val);
                
                TreeNode temp_node = null;
                int current_sum = 0;
                
                while(!nodes.isEmpty())
                {
                    temp_node = nodes.peek();
                    current_sum = path_sum.peek();
    
                    // if the current node is leaf , check if top of path_sum has the desired sum 
                    if(temp_node.left == null && temp_node.right == null)
                    {
                        if(current_sum == sum)
                            return true;
                        
                        temp_node = nodes.pop();
                        path_sum.pop();
                        
                        while(!nodes.isEmpty() && isParent(nodes.peek(),temp_node))
                        {
                            temp_node = nodes.pop();
                            path_sum.pop();
                        }
                        
                        continue;
                    }
                    
                    // if child nodes aren't null , push them to the stack and push their values with last cumulative in path_sum
                    if(temp_node.right != null)
                     {
                            nodes.push(temp_node.right);
                            path_sum.push(current_sum+temp_node.right.val);
                     }
                    if(temp_node.left != null)
                     {
                            nodes.push(temp_node.left);
                            path_sum.push(current_sum+temp_node.left.val);
                     }
                    
                }
            
            
            
            return false;
        }   
    }
    

    Explanation (Iterative version) -

    Assume the tree to be as shown below -

              5
            /   \
          4      8
                   \
                    13
    
    • We maintain 2 stacks - one for storing nodes and the other for
      path's sum(till that point).

    • Procedure for pushing values in both stacks -

      • Get the node at top of stack named nodes .Get the value of the sum till that node from top of stack named path_sum. ( So, current_sum = path_sum.peek())

      • If its right child is NOT null , insert node.right in nodes and insert current_sum + node.right.val in path_sum.

      • If its left child is NOT null , insert node.left in nodes and insert current_sum + node.left.val in path_sum.

    • Procedure for popping values from both stacks -

      • Popping starts ONLY when we hit a leaf node.

      • Once we come across a leaf node, we check whether current_sum (which was path_sum.peek()) is
        equal to the desired sum. If yes , then return true, else

        • pop that leaf node from nodes.Also do path_sum.pop() to remove the path sum till that point, as it is no longer required.

        • Now, since a leaf node is removed, we don't need to store its immediate parent too since its leaf didn't satisfy the condition. So, we keep popping values from nodes and path_sum until we hit a
          condition where last popped value has no relation with current node at top of the stack - nodes.

        • Popping finishes if in case stack is empty and we move out of it and return false. If popping doesn't finish, we repeat the entire procedure from step 1 again in a while loop.

    Following is the dry run for the above tree (assume desired_sum = 26) -

    nodes - 5 8 4

    path_sum - 5 13 9

    Now, 4 is leaf and 9 (top value of path_sum) != 26. So we pop values in a certain fashion as explained above.

    Current Status -

    nodes - 5 8

    path_sum - 5 13

    In the next step -

    nodes - 5 8 13

    path_sum - 5 13 26

    Now, 13 is leaf and 26 (top value of path_sum) = 26 (desired_sum) . So we return true.

    Hope I could put my point across. Happy Coding :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.