Given a binary tree where each node contains a positive integer, the task is to find the minimum number of nodes that need to be removed from the tree, such that the resulting tree has the same right view as the original tree.
Examples:
Input:
1
/ \
2 3
\ \
8 5
\
6Output: 2
Explanation: The right view of the given binary tree is [1, 3, 5, 6]. If we remove the nodes with values 2, and 8, the resulting tree will also have the same right view as the original tree.Input:
1
/ \
5 2
/ \
4 8
/ \
6 7Output: 3
Explanation: The right view of the original tree is [1, 2, 8, 7]. If we remove the nodes with values 5, 4, and 6, the resulting tree will also have the same right view as the original tree.
Approach: This can be solved with the following idea:
The first step is to find the rightmost node at each level of the binary tree. This can be achieved through a depth-first search traversal of the binary tree, where we traverse the right sub-tree first and then the left sub-tree. During this traversal, we maintain a vector called rightmost that stores the rightmost node at each level of the binary tree. The second step is to count the number of nodes that need to be removed to get the same right view as the original tree. This can be done through a recursive function count_to_remove that counts the number of nodes that need to be removed to get the same right view at each level of the binary tree. For each node in the binary tree, we check if its left and right children need to be removed by checking if their values match with the rightmost node at their respective levels. If they do not match, then we increment the count and recursively call count_to_remove on the child node. Finally, the min_nodes_to_remove function calls the traverse function to get the rightmost node at each level of the binary tree and then calls the count_to_remove function to count the minimum number of nodes that need to be removed to get the same right view as the original tree.
Steps of the above approach:
- We define a traverse function the purpose of this function is to traverse the binary tree in a depth-first fashion and store the rightmost value at each level in the rightmost vector.
- We call the traverse function on the root node of the binary tree, passing in an empty rightmost vector and level 0. This will populate the rightmost vector with the rightmost values at each level of the tree.
- We define a count_to_remove function the purpose of this function is to recursively count the number of nodes that need to be removed in order to make the tree’s right view match the rightmost vector.
- Within the count_to_remove function, we first check whether the current node is NULL. If so, we return 0, since there are no nodes to remove.
- Next, we recursively call count_to_remove on the left and right children of the current node, incrementing the level by 1 for each child. We also keep track of the total number of nodes to remove in a variable called count.
- For each child node, we check whether the rightmost value at its level matches the value of the child node. If not, we increment count by 1, since the child node must be removed in order to make the tree’s right view match the rightmost vector.
- Finally, we return the count from the count_to_remove function, which gives us the total number of nodes that need to be removed from the tree to make the right view match the rightmost vector.
- In the min_nodes_to_remove function, we call traverse to populate the rightmost vector and then call count_to_remove on the root node of the binary tree to get the total number of nodes to remove. We return this value from the function.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Structure of nodestruct Node { int val; Node* left; Node* right; Node(int x) : val(x), left(NULL), right(NULL) { }};// Traverse the treevoid traverse(Node* node, int level, vector<int>& rightmost){ if (!node) { return; } if (rightmost.size() == level) { rightmost.push_back(node->val); } traverse(node->right, level + 1, rightmost); traverse(node->left, level + 1, rightmost);}// Minimum nodes we can remove to keep// right view sameint count_to_remove(Node* node, int level, vector<int>& rightmost){ if (!node) { return 0; } int count = 0; if (node->left) { count += count_to_remove(node->left, level + 1, rightmost); if (rightmost[level] != node->val) { count++; } } if (node->right) { count += count_to_remove(node->right, level + 1, rightmost); if (rightmost[level] != node->val) { count++; } } // Return the number of nodes that // can be removed return count;}int min_nodes_to_remove(Node* root){ vector<int> rightmost; traverse(root, 0, rightmost); return count_to_remove(root, 0, rightmost);}// Driver codeint main(){ /* * Example: * 1 * / \ * 2 3 * \ \ * 8 5 * \ * 6 * */ Node* root = new Node(1); root->left = new Node(2); root->left->right = new Node(8); root->left->right->right = new Node(6); root->right = new Node(3); root->right->right = new Node(5); // Function call cout << min_nodes_to_remove(root) << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.List;class Node { int val; Node left; Node right; Node(int x) { val = x; left = null; right = null; }}class Main { // Traverse the tree static void traverse(Node node, int level, List<Integer> rightmost) { if (node == null) { return; } if (rightmost.size() == level) { rightmost.add(node.val); } traverse(node.right, level + 1, rightmost); traverse(node.left, level + 1, rightmost); } // Minimum nodes we can remove to keep right view same static int countToRemove(Node node, int level, List<Integer> rightmost) { if (node == null) { return 0; } int count = 0; if (node.left != null) { count += countToRemove(node.left, level + 1, rightmost); if (rightmost.get(level) != node.val) { count++; } } if (node.right != null) { count += countToRemove(node.right, level + 1, rightmost); if (rightmost.get(level) != node.val) { count++; } } // Return the number of nodes that can be removed return count; } static int minNodesToRemove(Node root) { List<Integer> rightmost = new ArrayList<>(); traverse(root, 0, rightmost); return countToRemove(root, 0, rightmost); } // Driver code public static void main(String[] args) { /* * Example: * 1 * / \ * 2 3 * \ \ * 8 5 * \ * 6 */ Node root = new Node(1); root.left = new Node(2); root.left.right = new Node(8); root.left.right.right = new Node(6); root.right = new Node(3); root.right.right = new Node(5); // Function call System.out.println(minNodesToRemove(root)); }}// This code is contributed by shivamgupta310570 |
Python3
# Python3 code for the above approach:class Node: def __init__(self, val): self.val = val self.left = None self.right = Nonedef traverse(node, level, rightmost): # If node is None, return if not node: return # If rightmost size is equal to level, append node value if len(rightmost) == level: rightmost.append(node.val) # Traverse right subtree traverse(node.right, level + 1, rightmost) # Traverse left subtree traverse(node.left, level + 1, rightmost)def count_to_remove(node, level, rightmost): # If node is None, return 0 if not node: return 0 count = 0 if node.left: # Recursively count the nodes to remove in the left subtree count += count_to_remove(node.left, level + 1, rightmost) # Increment count if the current node value is not equal to the rightmost value at the same level if rightmost[level] != node.val: count += 1 if node.right: # Recursively count the nodes to remove in the right subtree count += count_to_remove(node.right, level + 1, rightmost) # Increment count if the current node value is not equal to the rightmost value at the same level if rightmost[level] != node.val: count += 1 # Return the number of nodes that can be removed return countdef min_nodes_to_remove(root): # List to store the values of the rightmost nodes at each level rightmost = [] # Traverse the tree to populate the rightmost list traverse(root, 0, rightmost) # Count the minimum number of nodes to remove to keep the right view same return count_to_remove(root, 0, rightmost)# Driver code"""Example: 1 / \ 2 3 \ \ 8 5 \ 6"""root = Node(1)root.left = Node(2)root.left.right = Node(8)root.left.right.right = Node(6)root.right = Node(3)root.right.right = Node(5)# Function callprint(min_nodes_to_remove(root))# This code is contributed by shivamgupta0987654321 |
C#
// C# code for the above approach:using System;using System.Collections.Generic;public class Node{ public int val; public Node left; public Node right; public Node(int x) { val = x; left = null; right = null; }}public class GFG{ // Traverse the tree public static void Traverse(Node node, int level, List<int> rightmost) { if (node == null) { return; } if (rightmost.Count == level) { rightmost.Add(node.val); } Traverse(node.right, level + 1, rightmost); Traverse(node.left, level + 1, rightmost); } // Minimum nodes we can remove to keep // right view same public static int CountToRemove(Node node, int level, List<int> rightmost) { if (node == null) { return 0; } int count = 0; if (node.left != null) { count += CountToRemove(node.left, level + 1, rightmost); if (rightmost[level] != node.val) { count++; } } if (node.right != null) { count += CountToRemove(node.right, level + 1, rightmost); if (rightmost[level] != node.val) { count++; } } // Return the number of nodes that // can be removed return count; } public static int MinNodesToRemove(Node root) { List<int> rightmost = new List<int>(); Traverse(root, 0, rightmost); return CountToRemove(root, 0, rightmost); } // Driver code public static void Main(string[] args) { /* * Example: * 1 * / \ * 2 3 * \ \ * 8 5 * \ * 6 * */ Node root = new Node(1); root.left = new Node(2); root.left.right = new Node(8); root.left.right.right = new Node(6); root.right = new Node(3); root.right.right = new Node(5); // Function call Console.WriteLine(MinNodesToRemove(root)); }} |
Javascript
// JavaScript code for the above approach:// Node Structureclass Node { constructor(val) { this.val = val; this.left = null; this.right = null; }}function traverse(node, level, rightmost) { // If node is None, return if (!node) { return; } // If rightmost size is equal to level, append node value if (rightmost.length === level) { rightmost.push(node.val); } // Traverse right subtree traverse(node.right, level + 1, rightmost); // Traverse left subtree traverse(node.left, level + 1, rightmost);}function count_to_remove(node, level, rightmost) { // If node is None, return 0 if (!node) { return 0; } let count = 0; if (node.left) { // Recursively count the nodes to remove in the left subtree count += count_to_remove(node.left, level + 1, rightmost); // Increment count if the current node value is not equal to the rightmost value at the same level if (rightmost[level] !== node.val) { count += 1; } } if (node.right) { // Recursively count the nodes to remove in the right subtree count += count_to_remove(node.right, level + 1, rightmost); // Increment count if the current node value is not equal to the rightmost value at the same level if (rightmost[level] !== node.val) { count += 1; } } // Return the number of nodes that can be removed return count;}function min_nodes_to_remove(root) { // List to store the values of the rightmost nodes at each level const rightmost = []; // Traverse the tree to populate the rightmost list traverse(root, 0, rightmost); // Count the minimum number of nodes to remove to keep the right view same return count_to_remove(root, 0, rightmost);}// Driver code/*Example: 1 / \ 2 3 \ \ 8 5 \ 6*/const root = new Node(1);root.left = new Node(2);root.left.right = new Node(8);root.left.right.right = new Node(6);root.right = new Node(3);root.right.right = new Node(5);// Function callconsole.log(min_nodes_to_remove(root));// This code is contributed by Tapesh(tapeshdua420) |
Output
2
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Auxiliary Space: O(h), where h is the height of the binary tree.
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
