A tree is a heirarchial data structure that is described as a collection of nodes. The nodes are connected together to represent a hierarchy. It is a hierarchical structure since its pieces are placed at several levels. The tree is a popular topic asked in interviews, and one must practice questions to master this data structure. In this blog, we will talk about a tree-based problem in which we find the sum of the leaf nodes at minimum level.

Problem Statement

You are given a binary tree with n nodes. The goal is to get the sum of leaf nodes at minimum level in the tree.

Note: Minimum level does not mean the lowest level of the tree. Here, minimum means the lesser level. For example, between level 3 and level 5, the minimum level is 3.

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

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

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

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.

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.