Root to leaf path sum equal to a given number

Problem:Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given below is the tree and sum = 62

Output: Yes

5 -> 25 -> 11 -> 19

Method 1: Add all node to a queue and store sum value of each node to another queue. When it is a leaf node, check the stored sum value.

For the tree above, the queue would be: 5 - 9 - 27 - 14 - 11 - 19 - 21. It will check node 14, 19 and 21. This is a typical breadth first search(BFS) problem.

import java.util.*;

/* definetinon for creation of tree */
class Node 
{
    int data;
    Node left, right;
  
    Node(int item) 
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {

    Node root;

    public boolean hasPathSum(Node root, int sum) {

        /* handling base case */
        if(root == null) 
            return false;
 
        LinkedList<Node> nodes = new LinkedList<Node>();
        LinkedList<Integer> values = new LinkedList<Integer>();
 
        nodes.add(root);
        values.add(root.data);
 
        while(!nodes.isEmpty()) {
            Node curr = nodes.poll();
            int sumValue = values.poll();
 
            /* check if current node is root root and sum is 
               equal to required sum */
            if(curr.left == null && curr.right == null && sumValue==sum) {
                return true;
            }
 
            /* checking for left node */
            if(curr.left != null) {
                nodes.add(curr.left);
                values.add(sumValue + curr.left.data);
            }
 
            /* checking for right node */
            if(curr.right != null) {
                nodes.add(curr.right);
                values.add(sumValue + curr.right.data);
            }
        }
 
        return false;
    }

    /* driver method */
    public static void main(String args[]) 
    {
        int sum = 62;
         
        /* binary tree is
               5
             /   \
            9    27
           /      \
          14      11
                /   \
               19   21
        */
               
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(9);
        tree.root.right = new Node(27);
        tree.root.left.left = new Node(14);
        tree.root.right.right = new Node(11);
        tree.root.right.right.left = new Node(19);
        tree.root.right.right.right = new Node(21);
  
        if (tree.hasPathSum(tree.root, sum))
            System.out.println("There is a root to leaf path with sum " + sum);
        else
            System.out.println("There is no root to leaf path with sum " + sum);
    }
}

Output:

There is a root to leaf path with sum 62

Time Complexity: O(n)

Method 2: We can also do this problem using recursion. Below is the function program for recursion.

public boolean hasPathSum(TreeNode root, int sum) {

    /* handling base case */
    if (root == null)
        return false;

    /* if current node is leaf node */
    if (root.val == sum && (root.left == null && root.right == null))
        return true;
 
    /* recursing for left and right sub-tree */
    return hasPathSum(root.left, sum - root.val)
            || hasPathSum(root.right, sum - root.val);
}

Time Complexity: O(n)