Find Sum of All Left Leaves in a Given Binary Tree

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;
	}

You can also try this code with Online C++ Compiler

Run Code

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;
	}

You can also try this code with Online C++ Compiler

Run Code

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 tree, iterative preorder traversal of a Binary tree, Replace 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 LOT, Reverse Level Order Traversal, and Disjoint-set data structure.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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 problems, interview experiences, and interview bundle for placement preparations.

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

Happy Coding!