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

• 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 :)

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