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

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

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

Run Code

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.

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree
• Diameter Of Binary Tree

Happy Coding!