Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Left Sum

Easy
0/40
Average time to solve is 10m
profile
Contributed by
34 upvotes
Asked in companies
IBMAmazonMorgan Stanley

Problem statement

Given a binary tree having ‘N’ number of nodes. Your task is to find the sum of all left nodes present in the input binary tree. That is, you need to take the sum of all nodes which are the left child of some node.

Note :

1. A binary tree is a tree in which each node can have at most two children. 
2. The given tree will be non-empty i.e the number of non-NULL nodes will always be greater than or equal to 1.
3. Multiple nodes in the tree can have the same values, all values in the tree will be positive.
Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows. 
The first line of every test case contains elements of the Binary Tree in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For Example :

Consider the binary tree:


The input for the tree depicted in the above image would be :

3
5 1
6 2 0 8
-1 -1 7 4 -1 -1 -1 -1
-1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 3

Level 2 :
Left child of 3 = 5
Right child of 3 = 1

Level 3 :
Left child of 5 = 6
Right child of 5 = 2
Left child of 1 = 0
Right child of 1 = 8

Level 4 :
Left child of 6 = null (-1)
Right child of 6 = null(-1)
Left child of 2 = 7
Right child of 2 = 4
Left child of 0 = null (-1)
Right child of 0 = null (-1)
Left child of 8 = null (-1)
Right child of 8 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
Left child of 4 = null (-1)
Right child of 4 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
Output format :
For each test case, print the sum of all left nodes present  in the binary tree
The output of each test case should be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 5
1 <= ‘N’ <= 3 * (10 ^ 3)
1 <= ‘nodeVal’ <= 10 ^ 9
Where ‘N’ represents the number of nodes in a binary tree,
‘nodeVal’ represents the value of a node.

Time Limit: 1 sec.
Sample Input 1 :
2
3 5 1 6 2 0 8 -1 -1 7 4 -1 -1 -1 -1 -1 -1 -1 -1
1 2 3 4 5 -1 -1 6 -1 -1 -1 -1 -1
Sample Output 1 :
18
12
Explanation for Sample Input 1 :


Test Case 1 :
The nodes 5, 6, 7, and 0 are the only nodes that were the left child of any other node. S, they sum up to make the sum 18.


Test Case 2 :
The nodes 2, 4, and 6 are the only nodes that were the left child of any other node. S, they sum up to make the sum 12.
Sample Input 2 :
2
5 2 3 8 1 -1 -1 7 9 -1 -1 5 6 -1 -1 -1 -1 -1 -1
1 5 7 -1 -1 6 3 9 8 -1 -1 -1 -1 13 -1 -1 -1
Sample Output 2 :
22
33
Hint

Think of a recursive Approach.

Approaches (1)
Recursion

We just need to traverse the tree and store the sum of all left child, while visiting.

Algorithm :

  • First, make a recursive function say ‘leftSumHelper’ passing root and ‘isLeft’ as parameters. ‘isLeft’ is used to store and check if the node is a left node or not.
  • Declare a base condition to check if ‘root’ is NULL then return
  • Store the count of the number of left nodes by making a recursive call to the function passing root and ‘isLeft’ = 1 and storing the sum of nodes on left in a variable say ‘L’.
  • Store the count of the number of right nodes by making a recursive call to the function passing root and ‘isLeft’ = 0 and storing the sum of nodes on right in a variable say ‘R’.
  • Now check if ‘isLeft’ is 0 or not
    • If ‘isLeft’ is not equal to zero then return (L + R + root’s data) to the function.
    • Else return ('L' +' R').
Time Complexity

O(N), where ‘N’ is the number of nodes in the given tree.

 

As, we are making recursive calls N number of times. Therefore, overall time complexity will be O(N).

Space Complexity

O(1)

 

As we are using constant space. Therefore, space complexity will be O(1).

Code Solution
(100% EXP penalty)
Left Sum
All tags
Sort by
Search icon

Interview problems

Java Solution

public static long leftSum(BinaryTreeNode<Integer> root) 

    {

        /* 

          Write your code here

        */

        long[] arr = new long[1];

        findLeftSum(root,arr,false);

        return arr[0];

    }

    public static void findLeftSum(BinaryTreeNode<Integer> root,long[] arr,boolean flag)

    {

        if(root==null)

           return;

        if(flag)

           arr[0]+=root.data;

        findLeftSum(root.left, arr, true);

        findLeftSum(root.right, arr, false);

    }

3 views
0 replies
0 upvotes

Interview problems

C++ Recursive approach

#include <bits/stdc++.h> 

/*

    Tree Node class.

 

    class BinaryTreeNode 

    {

        T data;

        BinaryTreeNode<T> *left;

        BinaryTreeNode<T> *right;

 

        BinaryTreeNode(T data) {

            this->data = data;

            left = NULL;

            right = NULL;

        }

    }

*/

   

int countLeftNodes(BinaryTreeNode<int> *root) {

   

    if (root == NULL) return 0;

 

    int sum = 0;

 

    if (root->left) {

        sum += root->left->data;  

    }

 

    sum += countLeftNodes(root->left);

    sum += countLeftNodes(root->right);

 

    return sum;

}

 

long long leftSum(BinaryTreeNode<int> *root)

{

   

  int leftNodes=countLeftNodes(root);

  return leftNodes;

   

 

}

25 views
0 replies
0 upvotes
profile

Interview problems

c++ bfs

long long leftSum(BinaryTreeNode<int> *root) {

  vector<int> left;

  queue<BinaryTreeNode<int> *> q;

  q.push(root);

  while (q.empty() == false) {

    BinaryTreeNode<int> *temp = q.front();

    q.pop();

    if (temp->left) {

      left.push_back(temp->left->data);

      q.push(temp->left);

    }

    if (temp->right) {

      q.push(temp->right);

    }

  }

  int sum = 0;

  for (int i : left) {

    sum += i;

  }

  return sum;

}

57 views
0 replies
1 upvote

Interview problems

Using DFS || Easy C++ solution

long long sum;

void dfs(BinaryTreeNode<int> *node){

    if(node->left!=nullptr){

        sum+=node->left->data;

        dfs(node->left);

    }

    if(node->right!=nullptr){

        dfs(node->right);

    }

}

long long leftSum(BinaryTreeNode<int> *root)

{

    // Write your code here.

    sum = 0;

    dfs(root);

    return sum;

}

36 views
0 replies
0 upvotes

Interview problems

Best recursive Approach

long long leftSum(BinaryTreeNode<int> *root)
{
	if(!root)
		return 0;
	else if(root->left)
		return root->left->data + leftSum(root->left) + leftSum(root->right);
	else{
		return leftSum(root->right);
	}
}
47 views
0 replies
0 upvotes

Interview problems

Left Sum

 public static long leftSum(BinaryTreeNode<Integer> root) 

    {

        if(root==null)

        {

            return 0;

        }

 

        long sum=0;

        if(root.left!=null)

        {

            sum+=root.left.data;

        }

 

        sum+=leftSum(root.left);

        sum+=leftSum(root.right);

        return sum;

        

    }

52 views
0 replies
0 upvotes

Interview problems

C++ level order Traversal Approach::

long long leftSum(BinaryTreeNode<int> *root)

{     queue<BinaryTreeNode<int>*>q;

       q.push(root);

    long long sum=0;

    while(!q.empty())

    {

        int size =q.size();

        for(int i=0;i<size;i++)

        {

            BinaryTreeNode<int>*curr=q.front();

            q.pop();

            if(curr->left !=NULL)

            {

                sum+=curr->left->data;

                q.push(curr->left);

            }

            if(curr->right !=NULL)

            {

                q.push(curr->right);

            }

        }

    }

    return sum;

}

63 views
0 replies
0 upvotes

Interview problems

c++

long long leftSum(BinaryTreeNode<int> *root)

{

    // Write your code here.

    queue<BinaryTreeNode<int>*>q;

    q.push(root);

    int sum=0;

    while(!q.empty())

    {

        int size =q.size();

        for(int i =0;i<size;i++)

        {

            BinaryTreeNode<int>*first=q.front();

            q.pop();

            if(first->left)

            {

                sum+=first->left->data;

                q.push(first->left);

            }

            if(first->right)

            {

                q.push(first->right);

            }

        }

    }

    return sum;

}

91 views
0 replies
1 upvote

Interview problems

python solution

def leftSum(root):

 

    # Write you code here.

    q=[]

    k=0

    if root is None:

        return q

    s=[]

    s.append(root)

    while(s):

        node=s.pop(0)

        q.append(node.val)

        if node.left:

            k=k+node.left.val

            s.append(node.left)

        if node.right:

            s.append(node.right)

    return k

18 views
0 replies
0 upvotes

Interview problems

C++ SOLUTION [Recursive]

void inOrder(BinaryTreeNode<int> *root, long long &sum)
{
	if(root == NULL)
	    return;
	if(root->left != NULL)
	    sum += root->left->data;
	inOrder(root->left,sum);
	inOrder(root->right,sum);
}
long long leftSum(BinaryTreeNode<int> *root)
{
	long long sum = 0;
	inOrder(root,sum);
	return sum;
}

beginners

programming

113 views
0 replies
1 upvote
Full screen
Console