5
\$\begingroup\$

Root to leaf path sum equal to a given number

Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given number. Return false if no such path can be found.

I have written 3 solutions: one recursive, one using 2 stacks (DFS), and last one using 2 queues (BFS). I am looking for improvements and suggestions.

    // Recursive version
    public static boolean hasPathSum1 (Node root, int sum) { 
          if (root == null) {                                
              return false;
          }
          if(root.left == null && root.right == null && root.data == sum) {    
                return true;  
          }       
          return hasPathSum1(root.left, sum - root.data) ||
                 hasPathSum1(root.right, sum - root.data);
    }    
    //===========================================================================            
        // Iterative version (DFS) - Using 2 Stacks
        public static boolean hasPathSum2 (Node root, int sum) {
            if (root == null) {
                return false;
            }
        Stack<Node> nodes = new Stack<Node>();
        Stack<Integer> values = new Stack<Integer>();
        
        nodes.push(root);
        values.push(root.data);
        
        while (!nodes.isEmpty()) {
            Node current = nodes.pop();
            int sumValue = values.pop();
            
            if (current.left == null && current.right == null && sumValue == sum) {
                    return true;
            }
            if (current.left != null) {
                nodes.push(current.left);
                values.push(current.left.data + sumValue);
            }
            if (current.right != null) {
                nodes.push(current.right);
                values.push(current.right.data + sumValue);
            }
        }
        return false;
    }
//========================================================================        
    // Iterative version (BFS) - Using 2 queues
    public static boolean hasPathSum3 (Node root, int sum) {
        if(root == null) {
            return false;
        }
        Queue<Node> nodes = new LinkedList<Node>();
        Queue<Integer> values = new LinkedList<Integer>();
 
        nodes.add(root);
        values.add(root.data);
 
        while(!nodes.isEmpty()){
            Node current = nodes.remove();
            int sumValue = values.remove();
 
            if(current.left == null && current.right == null && sumValue == sum){
                return true;
            } 
            if(current.left != null){
                nodes.add(current.left);
                values.add(current.left.data + sumValue);
            } 
            if(current.right != null){
                nodes.add(current.right);
                values.add(current.right.data + sumValue);
            }
        }
        return false;
    }
\$\endgroup\$

4 Answers 4

7
\$\begingroup\$

If recursion has reached a leaf node then either you have accumulated the correct sum or not, but in no case it is necessary to check the left or right child node. Therefore I would change the first implementation slightly to

public static boolean hasPathSum1 (Node root, int sum) { 
      if (root == null) {                               
          return false;
      }
      if (root.left == null && root.right == null) {
          return root.data == sum;  
      }     
      return hasPathSum1(root.left, sum - root.data) ||
             hasPathSum1(root.right, sum - root.data);
}   

If the values of all nodes are non-negative then you can stop the search if the accumulated sum along a path is greater than the target sum:

public static boolean hasPathSum1 (Node root, int sum) { 
      if (sum < 0) {                               
          return false;
      }
      if (root == null) {                               
          return false;
      }
      if (root.left == null && root.right == null) {
          return root.data == sum;  
      }     
      return hasPathSum1(root.left, sum - root.data) ||
             hasPathSum1(root.right, sum - root.data);
}   

(and similarly for the iterative versions).

Some advice from the answers to your previous question DFS in Binary Tree applies here as well:

  • Better/consistent spacing: if and while is sometimes followed by a space (good) and sometime not (bad).
  • Rename the root parameter to node.
  • Make those methods instance methods of the Node class instead of static methods.
\$\endgroup\$
1
\$\begingroup\$

Here is an alternative stack version . You can reduce the the amount of branches in each iteration using the inner while emulating recursive pre-order walk. I haven't tested it so I may have overlook something.

Note: You can also add the check suggested by Martin R in case there are only positive values.

  public static boolean hasPathSum2(Node root, int sum)
  {

      Stack<Node> nodeS= new Stack<>();
      Stack<Integer> sumS= new Stack<>();
      Node current = root;
      int pathSum= 0;

      nodeS.add(null);
      sumS.add(0);

      while(!nodeS.empty())
      {   
          while(current!=null)
          {
              nodeS.push(current.right);
              pathSum +=  current.data;
              sumS.push(pathSum);
              current = current.left;
          }
          pathSum = sumS.pop();
          current = nodeS.pop();

          if(current == null && pathSum == sum)
              return true;

      }
      return false;
  }
\$\endgroup\$
1
\$\begingroup\$

First of all, for the readers: if a node's data can only be positive the evalutation can be cut short at places.

Recursive version

public static boolean hasPathSum1 (Node node, int sum) { 
    if (node == null) {                                
        return sum == 0;
    }
    sum -= node.data;
    return hasPathSum1(node.left, sum) ||
           hasPathSum1(node.right, sum);
}    

The initial argument is indeed the root node. However for a recursive function it is better to use node or subtree; root is not true.

Most importantly a sum 0 for a null tree should return true.

Your solution circumvents this by adding an extra case. Repeating sum - root.data is okay; I just showed an alternative.

Iterative version (DFS) - Using 2 Stacks

public static boolean hasPathSum2 (Node root, int sum) {
    if (root == null) {
        return sum == 0;
    }
    Stack<Node> nodes = new Stack<Node>();
    Stack<Integer> values = new Stack<Integer>();
    

Actually the class Stack has a bit old implementation. In production code better use:

Deque<Integer> stack = new ArrayDeque<>();

Instead of parallel stacks you could make a stack of a composed object. It would be a bit more clear, that they should be pushed and popped at the same time. Less error prone, better readable. Below I use the record class that was introduced for just these cases.

Also you need not check the original sum but can store the reduced sum.

    record NodeWithSum(Node node, int sumValue) { };
    Deque<NodeWithSum> todos = new ArrayDeque<>();
    
    todos.addLast(new NodesWithSum(root, sum - root.data)); // push
    
    while (!todos.isEmpty()) {
        NodeWithSum todo = todos.removeLast();
        
        if (todo.node.left == null && todo.node.right == null && todo.sumValue == 0) {
                return true;
        }

        if(todo.node.left != null){
            nodes.addLast(new NodesWithSum(todo.node.left, todo.sumValue - todo.node.left.data));
        } 
        if(todo.node.right != null){
            nodes.addLast(new NodesWithSum(todo.node.right, todo.sumValue - todo.node.right.data));
        }
    }
    return false;

Reviewing the third solution whould not shed more light.

\$\endgroup\$
0
\$\begingroup\$

As an improvement to the recursive approach you can do like this:

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root==null)  return false;
    if (root.left==null && root.right==null)  return (root.val==targetSum);
    return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
}

Here you're terminating when (root.left==null && root.right==null). It's an improvement for a recursive function.

You can use a few other approaches as an iterative solution. However rather than using two stacks or queues you can:

  1. use pairs or custom objects with one stack or queue

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root==null) {
            return false;
        }
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, targetSum-root.val));
        while(!queue.isEmpty()) {
            Pair<TreeNode, Integer> node = queue.poll();
            if (node.getValue()==0 && node.getKey().left==null && node.getKey().right==null) {
                return true;
            }
            if (node.getKey().left!=null) {
                queue.offer(new Pair<>(node.getKey().left, node.getValue()-node.getKey().left.val));
            }
            if (node.getKey().right!=null) {
                queue.offer(new Pair<>(node.getKey().right, node.getValue()-node.getKey().right.val));
            }
        }
        return false;
    }
    
  2. use only one queue or stack with replacing value of TreeNodes

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root==null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left==null && node.right==null) {
                if (node.val==targetSum) {
                    return true;
                }
            }
            if (node.right!=null) {
                node.right.val+=node.val;
                queue.offer(node.right);
            }
            if (node.left!=null) {
                node.left.val+=node.val;
                queue.offer(node.left);
            }
        }
        return false;
    }
    
\$\endgroup\$
1
  • \$\begingroup\$ This would probably be a great answer on stack overflow, but what Code Review is about is making meaningful observations about the original code to help the original poster improve their coding skills. On code review alternate code only solutions are considered poor answers and may be down voted or removed by the community. If you add some observations about why these 3 alternate solutions are better than the original code you have the beginning of a great answer on code review. Please see How do I write a good answer?. \$\endgroup\$
    – pacmaninbw
    Jan 20, 2022 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.