Print the Forests of a Binary Tree after removal of given Nodes
Given a Binary Tree and an array arr[] consisting of values of nodes to be deleted, the task is to print Inorder Traversal of the forests after deleting the nodes.
Examples:
Input: arr[] = {10, 5}
10 / \ 20 30 / \ \ 4 5 7Output:
4 20
30 7
Input: arr[] = {5}
1 / \ 5 6 / \ 10 12Output:
10
1 6 12
Approach: Follow the below steps to solve the problem:
- Perform the Postorder Traversal of the Binary Tree.
- For each node, check if it contains the value to be deleted.
- If found to be true, store its child as the root of the forest. Print the forest by Inorder Traversal.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Stores the nodes to be deletedunordered_map<int, bool> mp;// Structure of a Tree nodestruct Node { int key; struct Node *left, *right;};// Function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Function to check whether the node// needs to be deleted or notbool deleteNode(int nodeVal){ return mp.find(nodeVal) != mp.end();}// Function to perform tree pruning// by performing post order traversalNode* treePruning(Node* root, vector<Node*>& result){ if (root == NULL) return NULL; root->left = treePruning(root->left, result); root->right = treePruning(root->right, result); // If the node needs to be deleted if (deleteNode(root->key)) { // Store the its subtree if (root->left) { result.push_back(root->left); } if (root->right) { result.push_back(root->right); } return NULL; } return root;}// Perform Inorder Traversalvoid printInorderTree(Node* root){ if (root == NULL) return; printInorderTree(root->left); cout << root->key << " "; printInorderTree(root->right);}// Function to print the forestsvoid printForests(Node* root, int arr[], int n){ for (int i = 0; i < n; i++) { mp[arr[i]] = true; } // Stores the remaining nodes vector<Node*> result; if (treePruning(root, result)) result.push_back(root); // Print the inorder traversal of Forests for (int i = 0; i < result.size(); i++) { printInorderTree(result[i]); cout << endl; }}// Driver Codeint main(){ Node* root = newNode(1); root->left = newNode(12); root->right = newNode(13); root->right->left = newNode(14); root->right->right = newNode(15); root->right->left->left = newNode(21); root->right->left->right = newNode(22); root->right->right->left = newNode(23); root->right->right->right = newNode(24); int arr[] = { 14, 23, 1 }; int n = sizeof(arr) / sizeof(arr[0]); printForests(root, arr, n);} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Stores the nodes to be deletedstatic HashMap<Integer, Boolean> mp = new HashMap<>();// Structure of a Tree nodestatic class Node{ int key; Node left, right;};// Function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);}// Function to check whether the node// needs to be deleted or notstatic boolean deleteNode(int nodeVal){ return mp.containsKey(nodeVal);}// Function to perform tree pruning// by performing post order traversalstatic Node treePruning(Node root, Vector<Node> result){ if (root == null) return null; root.left = treePruning(root.left, result); root.right = treePruning(root.right, result); // If the node needs to be deleted if (deleteNode(root.key)) { // Store the its subtree if (root.left != null) { result.add(root.left); } if (root.right != null) { result.add(root.right); } return null; } return root;}// Perform Inorder Traversalstatic void printInorderTree(Node root){ if (root == null) return; printInorderTree(root.left); System.out.print(root.key + " "); printInorderTree(root.right);}// Function to print the forestsstatic void printForests(Node root, int arr[], int n){ for (int i = 0; i < n; i++) { mp.put(arr[i], true); } // Stores the remaining nodes Vector<Node> result = new Vector<>(); if (treePruning(root, result) != null) result.add(root); // Print the inorder traversal of Forests for (int i = 0; i < result.size(); i++) { printInorderTree(result.get(i)); System.out.println(); }}// Driver Codepublic static void main(String[] args){ Node root = newNode(1); root.left = newNode(12); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(23); root.right.right.right = newNode(24); int arr[] = { 14, 23, 1 }; int n = arr.length; printForests(root, arr, n);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 Program to implement# the above approach # Stores the nodes to be deletedmp = dict() # Structure of a Tree nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to create a new nodedef newNode(key): temp = Node(key) return temp # Function to check whether the node# needs to be deleted or notdef deleteNode(nodeVal): if nodeVal in mp: return True else: return False# Function to perform tree pruning# by performing post order traversaldef treePruning( root, result): if (root == None): return None; root.left = treePruning(root.left, result); root.right = treePruning(root.right, result); # If the node needs to be deleted if (deleteNode(root.key)): # Store the its subtree if (root.left): result.append(root.left); if (root.right): result.append(root.right); return None; return root;# Perform Inorder Traversaldef printInorderTree(root): if (root == None): return; printInorderTree(root.left); print(root.key, end=' ') printInorderTree(root.right); # Function to print the forestsdef printForests(root, arr, n): for i in range(n): mp[arr[i]] = True; # Stores the remaining nodes result = [] if (treePruning(root, result)): result.append(root); # Print the inorder traversal of Forests for i in range(len(result)): printInorderTree(result[i]); print() # Driver Codeif __name__=='__main__': root = newNode(1); root.left = newNode(12); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(23); root.right.right.right = newNode(24); arr = [ 14, 23, 1 ] n = len(arr) printForests(root, arr, n);# This code is contributed by rutvik_56 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Stores the nodes to be deletedstatic Dictionary<int, Boolean> mp = new Dictionary<int, Boolean>();// Structure of a Tree nodeclass Node{ public int key; public Node left, right;};// Function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);}// Function to check whether the node// needs to be deleted or notstatic bool deleteNode(int nodeVal){ return mp.ContainsKey(nodeVal);}// Function to perform tree pruning// by performing post order traversalstatic Node treePruning(Node root, List<Node> result){ if (root == null) return null; root.left = treePruning(root.left, result); root.right = treePruning(root.right, result); // If the node needs to be deleted if (deleteNode(root.key)) { // Store the its subtree if (root.left != null) { result.Add(root.left); } if (root.right != null) { result.Add(root.right); } return null; } return root;}// Perform Inorder Traversalstatic void printInorderTree(Node root){ if (root == null) return; printInorderTree(root.left); Console.Write(root.key + " "); printInorderTree(root.right);}// Function to print the forestsstatic void printForests(Node root, int []arr, int n){ for(int i = 0; i < n; i++) { mp.Add(arr[i], true); } // Stores the remaining nodes List<Node> result = new List<Node>(); if (treePruning(root, result) != null) result.Add(root); // Print the inorder traversal of Forests for(int i = 0; i < result.Count; i++) { printInorderTree(result[i]); Console.WriteLine(); }}// Driver Codepublic static void Main(String[] args){ Node root = newNode(1); root.left = newNode(12); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(23); root.right.right.right = newNode(24); int []arr = { 14, 23, 1 }; int n = arr.Length; printForests(root, arr, n);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript Program to implement the above approach // Stores the nodes to be deleted let mp = new Map(); // Structure of a Tree node class Node { constructor(key) { this.left = this.right = null; this.key = key; } } // Function to create a new node function newNode(key) { let temp = new Node(key); return (temp); } // Function to check whether the node // needs to be deleted or not function deleteNode(nodeVal) { return mp.has(nodeVal); } // Function to perform tree pruning // by performing post order traversal function treePruning(root, result) { if (root == null) return null; root.left = treePruning(root.left, result); root.right = treePruning(root.right, result); // If the node needs to be deleted if (deleteNode(root.key)) { // Store the its subtree if (root.left != null) { result.push(root.left); } if (root.right != null) { result.push(root.right); } return null; } return root; } // Perform Inorder Traversal function printInorderTree(root) { if (root == null) return; printInorderTree(root.left); document.write(root.key + " "); printInorderTree(root.right); } // Function to print the forests function printForests(root, arr, n) { for (let i = 0; i < n; i++) { mp.set(arr[i], true); } // Stores the remaining nodes let result = []; if (treePruning(root, result) != null) result.push(root); // Print the inorder traversal of Forests for (let i = 0; i < result.length; i++) { printInorderTree(result[i]); document.write("</br>"); } } let root = newNode(1); root.left = newNode(12); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(23); root.right.right.right = newNode(24); let arr = [ 14, 23, 1 ]; let n = arr.length; printForests(root, arr, n);</script> |
Output:
21 22 12 13 15 24
Time Complexity: O(N)
Auxiliary Space: O(N)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
