Given a binary tree with positive values of nodes, find the minimum number of nodes that need to be removed to transform it into a complete binary tree. Return 0 if the given tree is already complete.
Note: A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except possibly the lowest level nodes which are filled from as left as possible.
Examples:
Input:
Input example tree 1
Output: 1
Explanation: If we remove node 6, it will transform into the complete binary tree. Note that we could also remove all the nodes of the last level which will also convert it to complete but it will not be the minimum.Input:
Input example tree 2
Output: 3
Explanation: Nodes 6, 7, and 8 are to be removed.
Approach: To solve the problem using BFS (Breadth First Search) follow the below idea:
Using BFS (Breadth First Search): BFS is the most intuitive algorithm here. We will traverse through each level of the given binary tree and when we find the first null node after that all other nodes have to be removed (if present) to convert it to a complete binary tree, So we will count those nodes and return it as our answer.
Steps that were to follow the above approach:
- Start the BFS traversal with the root node.
- To keep track of the null node create a boolean “nullFound” with starting value of false.
- Now when the first null node is found make “nullFound” true.
- As soon as “nullFound” becomes true, count all preceding nodes of the same level as well as of below levels.
Below is the code to implement the above steps:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Definition for a binary tree nodestruct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};int minNodesToBeRemoved_bfs(TreeNode* root){ if (!root) return 0; // Initialize empty queue queue<TreeNode*> q; // push root and start bfs q.push(root); // Variable to store if null has // been found or not bool nullFound = false; int ans = 0; while (q.size()) { auto front = q.front(); q.pop(); if (front->left) { q.push(front->left); // If node is present and null // has been found increase the // answer by 1 if (nullFound) ans++; } // If node is null make // nullFound true else nullFound = true; // Do the same for right node if (front->right) { q.push(front->right); if (nullFound) ans++; } else nullFound = true; } // Return the answer return ans;}// Driver's codeint main(){ /* * * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->right = new TreeNode(6); root->left->right->left = new TreeNode(7); root->left->right->right = new TreeNode(8); cout << "Minimum number of nodes to be removed to make " "the tree complete is: "; // Function Call cout << minNodesToBeRemoved_bfs(root) << endl; return 0;} |
Python3
# Python code for the above approachfrom queue import Queue# Definition for a binary tree nodeclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef minNodesToBeRemoved_bfs(root: TreeNode) -> int: if not root: return 0 # Initialize empty queue q = Queue() # push root and start bfs q.put(root) # Variable to store if null has # been found or not nullFound = False ans = 0 while not q.empty(): front = q.get() if front.left: q.put(front.left) # If node is present and null # has been found increase the # answer by 1 if nullFound: ans += 1 # If node is null make # nullFound true else: nullFound = True # Do the same for right node if front.right: q.put(front.right) if nullFound: ans += 1 else: nullFound = True # Return the answer return ans# Driver's codeif __name__ == '__main__': """ * * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 """ root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.right = TreeNode(6) root.left.right.left = TreeNode(7) root.left.right.right = TreeNode(8) print("Minimum number of nodes to be removed to make " "the tree complete is: ", minNodesToBeRemoved_bfs(root)) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;// Definition for a binary tree nodepublic class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; left = null; right = null; }}public class Solution{ public static int minNodesToBeRemoved_bfs(TreeNode root) { if (root == null) return 0; // Initialize empty queue Queue<TreeNode> q = new Queue<TreeNode>(); // push root and start bfs q.Enqueue(root); // Variable to store if null has // been found or not bool nullFound = false; int ans = 0; while (q.Count > 0) { var front = q.Dequeue(); if (front.left != null) { q.Enqueue(front.left); // If node is present and null // has been found increase the // answer by 1 if (nullFound) ans++; } // If node is null make // nullFound true else nullFound = true; // Do the same for right node if (front.right != null) { q.Enqueue(front.right); if (nullFound) ans++; } else nullFound = true; } // Return the answer return ans; } // Driver's code static void Main() { /* * * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.right = new TreeNode(6); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(8); Console.Write("Minimum number of nodes to be removed to make " + "the tree complete is: "); // Function Call Console.WriteLine(minNodesToBeRemoved_bfs(root)); }} |
Java
// Java code to implement the above approachimport java.util.LinkedList;import java.util.Queue;// Definition for a binary tree nodeclass TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; left = null; right = null; }}public class GFG { public static int minNodesToBeRemoved_bfs(TreeNode root) { if (root == null) return 0; // initialize empty queue Queue<TreeNode> q = new LinkedList<>(); // push root and start bfs q.offer(root); // variable to store if null has been found or not boolean nullFound = false; int ans = 0; while (!q.isEmpty()) { TreeNode front = q.poll(); if (front.left != null) { q.offer(front.left); // if node is present and null has been // found increase the answer by 1 if (nullFound) ans++; } else // if node is null make nullFound true nullFound = true; // do the same for right node if (front.right != null) { q.offer(front.right); if (nullFound) ans++; } else nullFound = true; } // return the answer return ans; } // Driver's code public static void main(String[] args) { /* * * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.right = new TreeNode(6); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(8); System.out.print( "Minimum number of nodes to be removed to make the tree complete is: "); System.out.println(minNodesToBeRemoved_bfs(root)); }} |
Javascript
// Javascript code for the above approach// Definition for a binary tree nodeclass TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}function minNodesToBeRemoved_bfs(root) { if (!root) return 0; // Initialize empty queue const q = []; // push root and start bfs q.push(root); // Variable to store if null has // been found or not let nullFound = false; let ans = 0; while (q.length) { const front = q.shift(); if (front.left) { q.push(front.left); // If node is present and null // has been found increase the // answer by 1 if (nullFound) ans++; } // If node is null make // nullFound true else nullFound = true; // Do the same for right node if (front.right) { q.push(front.right); if (nullFound) ans++; } else nullFound = true; } // Return the answer return ans;}// Driver's code(() => { /* * * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ const root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.right = new TreeNode(6); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(8); console.log("Minimum number of nodes to be removed to make the tree complete is: "); // Function Call console.log(minNodesToBeRemoved_bfs(root));})(); |
Output
Minimum number of nodes to be removed to make the tree complete is: 3
Time Complexity: O(n), (n is the number of nodes) because we are traversing through all the nodes.
Auxiliary Space: O(n), (n is the number of nodes) queue is used to contain all the nodes.
Approach:
Using DFS (Depth First Search): Using DFS for this problem is a little bit tricky. We can not directly check, at which level the first null node is found as in the above approach. So we will create an array and store the elements of the given tree (level-wise) in it, at a specific index such that if the tree was complete all the nodes would be filled in the array before a null appears. After the first null node is found the count of all the preceding nodes is our answer.
Steps that were to follow the above approach:
- Find the height of the binary tree ‘h’ using DFS.
- For a complete tree, the maximum nodes can be (2h – 1).
- Create an array of size (2h – 1) to store nodes level-wise.
- Now start the DFS with root and keep filling the array.
- For all, DFS calls if the root is at index “idx” put the left node at index 2*idx+1 and the right node at 2*idx+2.
- Now traverse through the array and keep a track of the first null node.
- If there are any other nodes after the first null node count them and return.
Illustration of the above steps:
Given Tree:
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
- Height of the tree: 4, Maximum possible Nodes : 24 – 1 = 15.
- Initial Array: |-1| |-1| |-1| |-1| ….. 15 blocks.
- Array after DFS traversal: |1| |2| |3| |4| |5| |-1| |6| |-1| |-1| |7| |8| |-1| |-1| |-1| |-1|.
- The first null node found at index 5 after that nodes 6, 7 and 8 are present. So the answer is 3.
Below is the code to implement the above steps:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Definition for a binary tree nodestruct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};// Function to calculate the// height of the treeint height(TreeNode* root){ if (!root) return 0; return 1 + max(height(root->left), height(root->right));}// dfs traversal to fill the arrayvoid dfs(TreeNode* root, int index, vector<int>& arr){ if (!root) return; arr[index] = root->val; dfs(root->left, 2 * index + 1, arr); dfs(root->right, 2 * index + 2, arr);}int minNodesToBeRemoved_dfs(TreeNode* root){ int h = height(root); // Find the size of the array int maxNodes = (1 << h) - 1; // Make an array to store the // nodes level wise vector<int> arr(maxNodes, -1); // dfs call dfs(root, 0, arr); bool nullFound = false; int ans = 0; for (auto& it : arr) { // If the array value is -1 // means node is null if (it == -1) nullFound = true; // If node is present after the // first null was found // increase the answer if (nullFound && it != -1) ans++; } return ans;}// Drivers codeint main(){ /* * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->right = new TreeNode(6); root->left->right->left = new TreeNode(7); root->left->right->right = new TreeNode(8); cout << "Minimum number of nodes to be removed to make " "the tree complete is: "; // Function Call cout << minNodesToBeRemoved_dfs(root) << endl; return 0;} |
Java
// Java code to implement the above approachimport java.util.Arrays;class GFG { static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; left = null; right = null; } } // function to calculate the height of the tree static int height(TreeNode root) { if (root == null) return 0; return 1 + Math.max(height(root.left), height(root.right)); } // dfs traversal to fill the array static void dfs(TreeNode root, int index, int[] arr) { if (root == null) return; arr[index] = root.val; dfs(root.left, 2 * index + 1, arr); dfs(root.right, 2 * index + 2, arr); } static int minNodesToBeRemoved_dfs(TreeNode root) { int h = height(root); // find the size of the array int maxNodes = (1 << h) - 1; // make an array to store the nodes level wise int[] arr = new int[maxNodes]; Arrays.fill(arr, -1); // dfs call dfs(root, 0, arr); boolean nullFound = false; int ans = 0; for (int i = 0; i < arr.length; i++) { int it = arr[i]; // if the array value is -1 means node is null if (it == -1) nullFound = true; // if node is present after the first null was // found increase the answer if (nullFound && it != -1) ans++; } return ans; } public static void main(String[] args) { /* * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.right = new TreeNode(6); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(8); System.out.print( "Minimum number of nodes to be removed to make the tree complete is: "); System.out.println(minNodesToBeRemoved_dfs(root)); }} |
Python3
# Python3 code for the above approach# Definition for a binary tree nodeclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None# Function to calculate the# height of the treedef height(root): if not root: return 0 return 1 + max(height(root.left), height(root.right))# dfs traversal to fill the arraydef dfs(root, index, arr): if not root: return arr[index] = root.val dfs(root.left, 2 * index + 1, arr) dfs(root.right, 2 * index + 2, arr)def minNodesToBeRemoved_dfs(root): h = height(root) # Find the size of the array maxNodes = (1 << h) - 1 # Make an array to store the # nodes level wise arr = [-1] * maxNodes # dfs call dfs(root, 0, arr) nullFound = False ans = 0 for it in arr: # If the array value is -1 # means node is null if it == -1: nullFound = True # If node is present after the # first null was found # increase the answer if nullFound and it != -1: ans += 1 return ans# Drivers codeif __name__ == "__main__": """ 1 / \ 2 3 / \ \ 4 5 6 / \ 7 8 Output: 3 """ root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.right = TreeNode(6) root.left.right.left = TreeNode(7) root.left.right.right = TreeNode(8) print("Minimum number of nodes to be removed to make the tree complete is: ") # Function Call print(minNodesToBeRemoved_dfs(root)) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;// Definition for a binary tree nodepublic class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; left = null; right = null; }}public class Solution { // Function to calculate the height of the tree public int Height(TreeNode root) { if (root == null) { return 0; } return 1 + Math.Max(Height(root.left), Height(root.right)); } // dfs traversal to fill the array public void Dfs(TreeNode root, int index, List<int> arr) { if (root == null) { return; } arr[index] = root.val; Dfs(root.left, 2 * index + 1, arr); Dfs(root.right, 2 * index + 2, arr); } public int MinNodesToBeRemoved(TreeNode root) { int h = Height(root); // Find the size of the array int maxNodes = (1 << h) - 1; // Make an array to store the nodes level wise List<int> arr = new List<int>(maxNodes); for (int i = 0; i < maxNodes; i++) { arr.Add(-1); } // dfs call Dfs(root, 0, arr); bool nullFound = false; int ans = 0; foreach (int it in arr) { // If the array value is -1 means node is null if (it == -1) { nullFound = true; } // If node is present after the first null was found // increase the answer if (nullFound && it != -1) { ans++; } } return ans; } // Drivers code static void Main() { /* * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.right = new TreeNode(6); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(8); Console.Write("Minimum number of nodes to be removed to make " + "the tree complete is: "); // Function Call Console.WriteLine(new Solution().MinNodesToBeRemoved(root)); }} |
Javascript
// Javascript code for the above approach// Definition for a binary tree nodeclass TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}// Function to calculate the height of the treefunction height(root) { if (!root) { return 0; } return 1 + Math.max(height(root.left), height(root.right));}// dfs traversal to fill the arrayfunction dfs(root, index, arr) { if (!root) { return; } arr[index] = root.val; dfs(root.left, 2 * index + 1, arr); dfs(root.right, 2 * index + 2, arr);}function minNodesToBeRemoved_dfs(root) { const h = height(root); // Find the size of the array const maxNodes = (1 << h) - 1; // Make an array to store the nodes level wise const arr = new Array(maxNodes).fill(-1); // dfs call dfs(root, 0, arr); let nullFound = false; let ans = 0; for (let i = 0; i < arr.length; i++) { const it = arr[i]; // If the array value is -1 // means node is null if (it === -1) { nullFound = true; } // If node is present after the // first null was found // increase the answer if (nullFound && it !== -1) { ans++; } } return ans;}// Drivers codefunction main() { /* * 1 * / \ * 2 3 * / \ \ * 4 5 6 * / \ * 7 8 * * Output: 3 */ const root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.right = new TreeNode(6); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(8); console.log( "Minimum number of nodes to be removed to make " + "the tree complete is: " + minNodesToBeRemoved_dfs(root) );}main(); |
Output
Minimum number of nodes to be removed to make the tree complete is: 3
Time Complexity: O(2^h-1), where h is the height of the tree.
Auxiliary Space: O(2^h-1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
