A binary tree is a data structure that is used for storing data. It is made up of nodes that consist of values. A node can have two children nodes, i.e., left and right. A binary tree can have two utmost children. The topmost node is called the root node, while the node with no children is called the root node.

Problem Statement

The count of leaf nodes must be removed at each step to empty a given Binary Tree.

The problem statement asks us to remove the leaf nodes at each step. In the first iteration, starting from the root as we go downwards, we have to count the number of leaf nodes we remove at that time. Then in the second iteration, we will start again from the root node and count the number of leaf nodes we have to remove present at that time after removing the leaf nodes present in the first iteration.

For Example

Input

Output

2 3 2 1

Explanation

In the first iteration, the leaf nodes are: {2,1} count = 2

In the second iteration removing the leaf nodes: {6,8,7} count = 3

In the third iteration for removing the leaf nodes: {4,5} count = 2

In the fourth iteration for removing the leaf nodes: {3} count = 1

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

Brute-force Approach

For the given problem statement, the brute force approach will traverse the binary tree for each operation and count the leaf nodes present at that time in the binary tree. After that, delete the leaf nodes from the given binary tree. But the Brute-force approach will result in greater time complexity that will be O(N*N) as we traverse each node every time. And space complexity of the brute force approach will be O(1).

Optimized Approach

We must understand that a leaf node is deleted only when the left and right children have been deleted to optimize the approach. To know at which step the node must be deleted, we need to know the maximum path length from the current node to the leaf node in that subtree. As the leaf node we must delete will be present in the deepest path, we need max path length.

Below is the implementation in c++

Code

#include <iostream>
#include <vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
//Node of the Binary Search tree
struct NinjaNode {
int data;
NinjaNode* left;
NinjaNode* right;
};
// finding the maximum height and then storing it in a vector of vectors
void MaxHeight(NinjaNode* curr, vector<vector<int>>& nodesByHeight, int height = 0) {
if (curr == NULL) {
return;
}
// new vector for the current height if it doesn't exist yet
if (height >= nodesByHeight.size()) {
nodesByHeight.push_back(vector<int>());
}
// Add the current node to the vector for its height
nodesByHeight[height].push_back(curr->data);
// Recursively process the left and right subtrees
MaxHeight(curr->left, nodesByHeight, height + 1);
MaxHeight(curr->right, nodesByHeight, height + 1);
}
// function for determining the count of the number of Ninjanodes that need to be deleted
void displayAndDelete(NinjaNode* root) {
// for storing the nodes at each height
vector<vector<int>> nodesByHeight;
// function calls for determining the maximum height from the leaf at that current Ninjanode.
MaxHeight(root, nodesByHeight);
vector<int>ans;
// Printing the answer.
for (int i = 0; i < nodesByHeight.size(); i++) {
ans.push_back(nodesByHeight[i].size());
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
}
int main() {
// creating the binary tree.
NinjaNode* root = new NinjaNode{3,
// left subtree
new NinjaNode{4, new NinjaNode{6, nullptr, nullptr},
new NinjaNode{8, new NinjaNode{2, nullptr, nullptr}, new
NinjaNode{1, nullptr, nullptr}}},
// right subtree
new NinjaNode{5, nullptr,
new NinjaNode{7, nullptr, nullptr}}
};
// Calling the function and displaying the answer.
cout << "The result is ";
displayAndDelete(root);
return 0;
}

Output

Explanation

In the above approach, we have defined a NinjaNode class representing the node in the binary tree. The MaxHeight is a recursive function that traverses the binary tree and stores the leaf nodes at each height in the vector of vector nodesByHeight. In the MaxHeight function, we will simply return nothing if the node is null. If the current height is less than or equal to a vector of vectors nodesByHeight, we add a new vector to nodesByHeight for storing nodes at that particular height. The current node is added to the vector due to its height. The maxHeight function is also called recursively on the left and right subtrees. The display and delete function counts the number of nodes to be deleted. It calls the MaxHeight function for determining the maximum height from the leaf at that current Ninjanode. Ans vector is used for storing the number of nodes at that particular height. The Ans is reversed to get the desired result. Therefore, in simple terms, we are traversing the binary tree and storing nodes at each height in the vector of vectors. After that, we count the number of nodes at each height and print the counts after storing them in an array in reverse order. So this gives us the desired output, that is, the number of leaf nodes we need to remove from the tree.

Complexity

The overall time complexity will be O(n), and space complexity will be O(h), where h is the height of the binary tree, as it stores the ans vector with a length equal to the height of the binary tree.

Frequently Asked Questions

What is a Binary Tree?

A binary tree is a data structure that is used for storing data. It is made up of nodes that consist of values. A node can have two children nodes, i.e., left and right.

What is a leaf node?

A leaf node can be defined as a node that does not have any child nodes.

How height of a tree is different from the depth of a tree?

The height of a tree can be defined as the longest path to a leaf. Whereas the depth of a tree can be defined as the length of the path to the root of the tree.

Conclusion

So, this blog discussed the problem of determining the count of leaf nodes required to be removed at each step to empty a given Binary Tree. To discover more, go to Coding Ninjas Studio to practice problems and ace your interviews like a Ninja! In today's competitive environment, more than memorizing a handful of questions is required. So, take our mock tests to evaluate where you stand among your peers and what areas you need to work on.