Last Updated: 1 Dec, 2020

Left Sum

Easy

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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').

Solve now