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\$
6
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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