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)

Print Left View of a Binary Tree

Problem: Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side.

For example: Given the following tree, the left view of tree is 5, 9, 14, 19

Method 1: The naive approach is to do level order traversal of the binary tree and print the first node of all the levels.

Method 2: We can also do this problem using recursion. The idea is to keep track of maximum level and the current level. Whenever current level is greater than the maximum level so far obtained, we print the current node because this is the first node in its level.

Below is the implementation of the idea.

#include <bits/stdc++.h>
using namespace std;
 
struct node
{
    int data;
    node *left;
    node *right;
};
 
/* utility function to create a new Binary Tree node */
node* newNode(int data)
{
    node *temp = new node();
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
/* function to print the left view of the binary tree */
void leftView(node *root, int *max_level, int cur_level)
{
    /* base case */
    if(root == NULL)
        return;
 
    /* if the current node is first node in level */
    if(*max_level < cur_level)
    {
        cout<<root->data<<" ";
        *max_level = cur_level;
    }
 
    /* recursive call for left and right sub tree */
    leftView(root->left, max_level, cur_level + 1);
    leftView(root->right, max_level, cur_level + 1);
}
 
/* driver function */
int main()
{
    node *root                = newNode(5);
    root->left                = newNode(9);
    root->right               = newNode(27);
    root->left->left          = newNode(14);
    root->right->right        = newNode(11);
    root->right->right->left  = newNode(19);
    root->right->right->right = newNode(21);
 
    int max_level = 0;
    leftView(root, &max_level, 1);
    cout<<"\n";
 
    return 0;
}

Output:

5 9 14 19

Time Complexity: O(n)