1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Brute-force Approach
3.2.
Optimized Approach
3.2.1.
Code
3.2.2.
Output
3.2.3.
Explanation
3.2.4.
Complexity
4.
4.1.
What is a Binary Tree?
4.2.
What is a leaf node?
4.3.
How height of a tree is different from the depth of a tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count of leaf nodes required to be removed at each step to empty a given Binary Tree

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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;

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

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.

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.

Recommended problems -

Happy Coding!

Live masterclass