Sum of Leaf Nodes at Minimum Level

Problem Example

Output: 102

The tree's leaf nodes at the minimum level are 10, 19, 31, and 42. The sum of the leaf nodes at minimum level of this tree is 102.

Output: 6

The leaf nodes at the minimum level in the tree are 6, and the sum is 6.

Brute force approach

Find the first level containing a leaf node by doing iterative level order traversal using a queue. After adding up all the leaf nodes at this level, stop traversing further.

Pseudocode

• First, we create the binary tree.
• Then we will check if the binary tree is empty or not. If yes, we return 0. Else, carry on.
• Then we will check if the binary tree has only one element. If yes, we return the root of the tree. Else carry on.
• We will create a queue for the level order traversal of the tree.
• Then we set the flag to 0 and check for the leaf nodes.
• When we encounter the leaf nodes at the minimum level, we accumulate them to the sum.
• After getting the required sum, we set the flag value to 1 to indicate the minimum level has been reached, and no further check is needed.
• Return the sum.

Implementation

// implementation in C++ to find the sum of leaf nodes at minimum level
#include <bits/stdc++.h>
using namespace std;


// structure of the node 
struct Node {
	int dat;
	Node *left, *right;
	};


// function to get a new node
Node* getNode(int dat)
{
	//allocate space
	Node* newNode = (Node*)malloc(sizeof(Node));


	// inserting the data
	newNode->dat = dat;
	newNode->left = newNode->right = NULL;
	return newNode;
}


// function to find the sum of leaf nodes at minimum level
int sumOfLeafNodesAtTheMinimumLevel(Node* root)
{
	// if tree is empty
	if (!root)
		return 0;

// if there is only one node
if (!root->left && !root->right)
	return root->dat;

// queue used for level order traversal
queue<Node*> queue;
int sum = 0;
bool flag = 0;


// push root node in the queue 'queue'
queue.push(root);


while (flag == 0) {

	// count number of nodes in the
	// current level
	int nc = queue.size();


	// traverse the current level nodes
	while (nc--) {

		// get front element from 'queue'
		Node* top = queue.front();
		queue.pop();

		// if it is a leaf node
		if (!top->left && !top->right) {

			// accumulate dat to 'sum'
			sum += top->dat;

			// set flag to 1 to signify minimum level for leaf nodes has been encountered
			flag = 1;
			}
			
		else {

			// if top's left and right child exists, push them to 'queue'
			if (top->left)
				queue.push(top->left);
			if (top->right)
				queue.push(top->right);
			}
		}
}


	// required sum
	return sum;
}


// Driver code
int main()
{
// binary tree creation
Node* root = getNode(1);
root->left = getNode(3);
root->right = getNode(4);
root->left->left = getNode(6);
root->left->right = getNode(5);
root->right->left = getNode(8);
root->right->right = getNode(3);
root->left->right->left = getNode(11);
root->right->left->right = getNode(10);

cout << "Sum of leaf nodes at minimum level = "
<< sumOfLeafNodesAtTheMinimumLevel(root);

return 0;
}

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

Run Code

Output

Sum of leaf nodes at minimum level = 9

Complexity analysis

Time complexity: O(n), n is the number of elements in the tree. It is of the order of O(n) because we have to do an iterative tree traversal.

Space complexity: O(n), n is the number of elements present in the tree. It is of the order of O(n) because we have to allocate new space for the tree.

Optimized approach

In this approach, we'll apply binary tree traversal. We will use a variable in to monitor the levels of each node. We will also use a hashmap, whose key is our level value. The value part of the hashmap will be used as a vector to store the node's data for that specific level. If the current node is a leaf node, we will push into the map with the key as level and the node's contents into a vector for each recursive iteration, increasing the level variable for each one. Once we have our map, all we need to do is add the vector of the first element.

Pseudocode

• First, we create the binary tree.
• Then we create a map as map <int, vector <int>>. Here the key will hold the level value, and the data part will hold the leaf nodes at that level.
• We traverse the tree recursively and check for the leaf nodes at each level. If we encounter a leaf node, we push the node into the vector. 
• After traversing the tree, we check for the minimum level of the tree and get the sum for the vector at that level.
• Return the sum.

Implementation

// implementation in C++ to find the sum of leaf nodes at minimum level
#include <bits/stdc++.h>
using namespace std;

struct Node {
	int dat;
	Node *left, *right;
	};

// function to get a new node
Node* getNode(int dat)
{
	// allocate space
	Node* newNode = (Node*)malloc(sizeof(Node));

	// put in the data
	newNode->dat = dat;
	newNode->left = newNode->right = NULL;
	return newNode;
}

	map <int, vector <int>> map_;
	void solve(Node* root, int level) {
	
	if(root == NULL)
		return;
		
	if(root->left == NULL && root->right == NULL)
		map_[level].push_back(root->dat);
		
	solve(root->left, level+1);
	solve(root->right, level+1);
	}
int sumOfLeafNodesAtTheMinimumLevel(Node *root)
{
	solve(root, 0);
	int sum = 0;
	for(auto i:map_) {
		for(auto j:i.second) {
			sum += j;
		}
	return sum;
	}
}

int main() {
// binary tree creation
Node* root = getNode(1);
root->left = getNode(4);
root->right = getNode(3);
root->left->right = getNode(2);
root->left->left = getNode(6);
root->right->right = getNode(11);
root->right->left = getNode(8);
cout << "Sum of leaf nodes at minimum level = "
<< sumOfLeafNodesAtTheMinimumLevel(root);
return 0;
}

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

Run Code

Output: 

Sum of leaf nodes at minimum level = 27

Complexity analysis

Time complexity: O(logn), where n is the number of elements in the tree. It is of the order of O(logn) because we have to recursively travel the tree.

Space complexity: O(n), n is the number of elements in the tree. It is of the order of O(n) because we have to allocate new space for the tree.

Check out this problem - Diameter Of Binary Tree

Frequently Asked Questions

What is the difference between a binary tree and a binary search tree?

A binary tree is a type of tree in which the elements have at most 2 children. It does not follow any particular order. The elements in the binary search tree can also have at most 2 children, but it follows a particular order. The elements on the left side of a specific element are smaller than that element, and the elements on the right side of an element are bigger than that element.

How do we allocate space for a new node?

We can allocate space for a node using Node* newNode = (Node*)malloc(sizeof(Node)).

How do we check for a leaf node?

For a leaf node, we check for the children of the node. If both the left and right nodes of the parent node are NULL, it is a leaf node. We can check it by using if (!node->left && !node->right). If yes, then it is a leaf node.

Conclusion

In this blog, we looked at a popular problem in which we find the sum of leaf nodes at minimum level.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning, 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 if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. You must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

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