Path sum in binary tree

Question

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;
    }

Answer 1

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.

Answer 2

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;
  }

Answer 3

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.

Answer 4

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;
   }