Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach 1(Pre-order traversing)
2.1.
Algorithm 
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Approach 2 (Breadth-first Traversal Approach)
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Approach 3 (Depth-first traversing)
4.1.
Algorithm
4.2.
Implementation
4.2.1.
Time Complexity
4.2.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What are the different types of traversal techniques used in binary trees?
5.2.
What is pre-order traversal in a binary tree?
5.3.
Why are the time and space complexity of the approach given above linear?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find Sum of All Left Leaves in a Given Binary Tree

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Finding the sum of all left leaves in a given binary tree is a binary tree problem. It is a type of question that check the critical thinking and aptitude of the candidate. It also checks his grasp on the concept of binary trees and how well versed the candidate is in this concept.

In order to find the sum of all left leaves in a given binary tree, we will be using three approaches, the first will be a pre-order traversing, the second will be Breadth-first traversal and the last would be Depth-first traversal

Problem Statement

We need to calculate the total number of leaf nodes in a binary tree. Each node in the binary tree must be traversed in order to determine whether the current node is a left-leaf node or not. 

A node is a left leaf node if both the left and right child pointers of the current node are NULL and the current node is the left child of its parent.

Sample Examples

Example 1

Output

Explanation

We are traversing the whole tree, and we are finding the left leaf nodes present in the binary tree. Here only the node ‘7’ is present in the binary tree as the left leaf node. Then we’ll return that.

 

Example 2

Output

Explanation

We are traversing the whole tree, and we are finding the left leaf nodes present in the binary tree. Here the nodes ‘17’ and ‘77’ are present as the left leaf nodes of the binary tree. Then we’ll return that.

Approach 1(Pre-order traversing)

In this approach, we’ll traverse the tree in a pre-order fashion. Afterward, we’ll sum all the left leaves nodes that we found in the process.

Algorithm 

  1. Pre-order traverse the binary tree that has been given.
  2. A left leaf node should be present, so verify that. A binary tree node is a leaf node if and only if:
    • if the current node is the parent's left child.
    • if the current node's left and right child pointers are NULL.
  3. Add its value to the variable sum if the current node is a leaf node on the left.
  4. Recursively calculate the sum of the left leaf nodes in the left and right subtrees and return if the current node is not a left leaf node.

Implementation

#include <stdio.h>
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;

struct node 
	{
    	int data;
    	struct node *left;
    	struct node *right;
	};
 
struct node* getNewNode(int data) 
	{
	  	/* dynamically allocate memory for a new node */
	  	struct node* newNode = (struct node*)malloc(sizeof(struct node));
  
	  	/* populate data in new Node */
	  	newNode->data = data;
	  	newNode->left = NULL;
	  	newNode->right = NULL;
   
  		return newNode;
	}
 
struct node* generateBTree()
	{
    	// Root Node
    	struct node* root =  getNewNode(1);
    	root->left = getNewNode(2);
    	root->right = getNewNode(3);
    	root->left->left = getNewNode(4);
    	root->left->right = getNewNode(5);
    	root->right->right = getNewNode(6);
    	root->left->left->left = getNewNode(7);
    	root->left->left->right = getNewNode(8);
    	return root;
	}
 
int isLeafNode(struct node *nodePtr)
	{
 		if(nodePtr == NULL)
    		return 0;
 		else if (nodePtr->left == NULL && nodePtr->right == NULL)
    		return 1;
 		else
    		return 0;
	}
	
	/* This function calculates sum of all left leaf nodes in a binary tree */
int getleftLeafsSum(struct node *root) 
	{
    	int sum = 0;
    	if (root != NULL) 
    	{
       		/*Check if left node of root is a leaf node */
       		if (isLeafNode(root->left)) 
       			{
           			/* Add left leaf node data to sum */
        			sum += root->left->data;
       			} 
       		else 
       			{
        			/* Recursively find sum of all left leaf nodes in left sub tree */
           			sum += getleftLeafsSum(root->left);
       			}
  
        	/* Recursively find sum of all left leaf nodes in left sub tree */
    	    sum += getleftLeafsSum(root->right);
    	}
    /* Now we’ll return sum of all left leaf nodes in a tree whose root node is root */
    	return sum;
	}
 
int main() {
    struct node *root = generateBTree();    
    cout<<"Left Leaf Sum : "<< getleftLeafsSum(root);
      return 0; 
}

 

Output

Time Complexity

Pre-order traversing is used to traverse through the binary tree, that’s why the time complexity of the approach is O(n).

Space Complexity

Pre-order traversing is used to traverse through the binary tree, and we know that pre-order traversing takes O(n), auxiliary space, so the space complexity of the approach is O(n).

Also check out - Inorder Predecessor

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2 (Breadth-first Traversal Approach)

We can use breadth-first traversal and keep a separate variable to indicate whether a node's children are left or right. When we come across a leaf, we determine whether it is the left or right child of its parent. If it is a left child, its value is added to the sum.

Algorithm

  1. Traverse the binary tree in a breadth-first manner.
  2. Put the values of the binary tree in a queue.
  3. A left leaf node should be present, so verify that. A binary tree node is a leaf node if and only if:
    • if the current node is the parent's left child.
    • if the current node's left and right child pointers are NULL.
  4. Add its value to the variable sum if the current node is a leaf node on the left.
  5. Recursively calculate the sum of the left leaf nodes in the left and right subtrees and return if the current node is not a left leaf node.

Implementation

#include <bits/stdc++.h>
using namespace std;

class Node 
	{
		public:
		int key;
		Node *left, *right;

		Node(int key_)
		{
			key = key_;
			left = NULL;
			right = NULL;
		}
	};

int getleftLeafsSum(Node* root)
	{
		if (root == NULL)
		return 0;

		queue<pair<Node*, bool> > q;
		q.push({ root, 0 });
		int sum = 0;

		while (!q.empty()) 
		{
			Node* temp = q.front().first;
			bool is_left_child = q.front().second;
			q.pop();

			if (!temp->left && !temp->right && is_left_child)
			sum = sum + temp->key;

			if (temp->left) 
				{
					q.push({ temp->left, 1 });
				}	

			if (temp->right) 
				{
					q.push({ temp->right, 0 });
				}
		}
		return sum;
	}

int main()
	{
		Node* root =  new Node(1);
			root->left = new Node(2);
    		root->right = new Node(3);
     		root->left->left = new Node(4);
     		root->left->right = new Node(5);
     		root->right->right = new Node(6);
     		root->left->left->left = new Node(7);
     		root->left->left->right = new Node(8);

		cout << "Left leaf sum: " << getleftLeafsSum(root) << endl;
		return 0;
	}

Output

Time Complexity

Breadth-first traversing is used to traverse through the binary tree, that’s why the time complexity of the approach is O(n).

Space Complexity

Breadth-first traversing is used to traverse through the binary tree, and we know that breadth-first traversing takes O(n), auxiliary space, so the space complexity of the approach is O(n).

Approach 3 (Depth-first traversing)

The idea is to use a stack to perform Depth-First Traversal on the tree (either Inorder, Preorder, or Postorder) and check if the Left Child is a Leaf node. If it is, then add the value of the node to the sum variable.

Algorithm

  1. Traverse the binary tree in a depth-first manner.
  2. Push the values of the binary tree in the stack.
  3. A left leaf node should be present, so verify that. A binary tree node is a leaf node if and only if:
    • if the current node is the parent's left child.
    • if the current node's left and right child pointers are NULL.
  4. Add its value to the variable sum if the current node is a leaf node on the left.
  5. Recursively calculate the sum of the left leaf nodes in the left and right subtrees and return if the current node is not a left leaf node.

Implementation

#include<bits/stdc++.h>
using namespace std;

class Node
	{
		public:
		int key;
		Node* left, *right;

		Node(int key_)
		{
			key = key_;
			left = NULL;
			right = NULL;
		}
	};

int getleftLeafsSum(Node* root)
	{
		if(root == NULL)
		return 0;

		stack<Node*> stack_;
		stack_.push(root);

		int sum = 0;

		while(stack_.size() > 0)
			{
				Node* currentNode = stack_.top();
				stack_.pop();

				if (currentNode->left != NULL)
					{
						stack_.push(currentNode->left);

						if(currentNode->left->left == NULL &&
						currentNode->left->right == NULL)
							{
								sum = sum + currentNode->left->key ;
							}
					}
				if (currentNode->right != NULL)
				stack_.push(currentNode->right);
			}

		return sum;
	}


int main()
	{
		Node* root =  new Node(1);
    		root->left = new Node(2);
    		root->right = new Node(3);
    		root->left->left = new Node(4);
    		root->left->right = new Node(5);
    		root->right->right = new Node(6);
    		root->left->left->left = new Node(7);
    		root->left->left->right = new Node(8);
		cout << "Left leaf sum: " << getleftLeafsSum(root) << endl;
		return 0;
	}

Output

Time Complexity

Depth-first traversing is used to traverse through the binary tree, that’s why the time complexity of the approach is O(n).

Space Complexity

Depth-first traversing is used to traverse through the binary tree, and we know that depth-first traversing takes O(n), auxiliary space, so the space complexity of the approach is O(n).

Frequently Asked Questions

What are the different types of traversal techniques used in binary trees?

There are three types of traversing techniques, pre-order, in-order, and post-order.

What is pre-order traversal in a binary tree?

Pre-order traversal means a root node is visited, then the left sub-tree, and then the right sub-tree is visited.

Why are the time and space complexity of the approach given above linear?

This approach's time and space complexity are linear, i.e., O(n), because we use pre-order traversing to traverse through the binary tree. And the time and space complexity of pre-order traversing is linear.

Conclusion

In this blog, we discussed a coding problem involving the pre-order approach to Find the sum of all left leaves in a given binary tree. We discussed the time and space complexity of the approach as well.

We hope that this blog has helped you enhance your knowledge about the problem to find the sum of all the parent nodes having child node x and other similar binary tree problems. After reading about the approach to solving the sum of all the parent nodes having child node x and similar problems. Don’t you want to learn more? Check out our articles inorder successor in a binary treeiterative preorder traversal of a Binary treeReplace each node in a binary tree with the sum of its inorder predecessor and successor, and many more on our Website.

Here are some coding problems that you must practice in order to have better understanding of binary trees, please look at these similar problems to learn more: Level Order Traversal, Specific LOTReverse Level Order Traversaland Disjoint-set data structure.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Do upvote our blogs if you find them helpful and engaging!

Happy Coding!

Previous article
Sum of all nodes of the given perfect binary tree
Next article
Find the sum of all right leaves in a given Binary Tree
Live masterclass