Given a Binary Tree, the task is to remove all the subtrees that do not contain any odd valued node. Print the Levelorder Traversal of the tree after removal of these subtrees.
Note: Print NULL for removed nodes.
Examples:
Input: Below is the given Tree:
1
\
2
/ \
8 5
Output: 1 NULL 2 NULL 5
Explanation:
Tree after pruning:
1
\
2
\
5Input: Below is the given Tree:
1
/ \
2 7
/ \ / \
8 10 12 5
Output: 1 NULL 7 NULL 5
Explanation:
Tree after pruning:
1
\
7
\
5
Approach: To solve the given problem, the idea is to traverse the tree using DFS Traversal and a concept of backtracking will be used. Follow the below steps to solve the problem:
- Traverse the given tree using DFS Traversal and perform the following steps:
- If the root node is NULL, then return.
- If the leaf node value is even, then remove this node by returning NULL. Otherwise, return the root node from the current recursive call.
- Recursively update the left and the right subtrees using the above conditions.
- After completing the above steps, print the updated tree using the level order Traversal with NULL in place of removed nodes.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Node of the treestruct node { int data; struct node *left, *right;};// Function to create a new nodenode* newNode(int key){ node* temp = new node; temp->data = key; temp->left = temp->right = NULL; return (temp);}// Function to print tree level wisevoid printLevelOrder(node* root){ // Base Case if (!root) return; // Create an empty queue for // level order traversal queue<node*> q; // Enqueue Root q.push(root); while (!q.empty()) { // Print front of queue and // remove it from queue node* temp = q.front(); cout << temp->data << " "; q.pop(); // If left child is present if (temp->left != NULL) { q.push(temp->left); } // Otherwise else if (temp->right != NULL) { cout << "NULL "; } // If right child is present if (temp->right != NULL) { q.push(temp->right); } // Otherwise else if (temp->left != NULL) { cout << "NULL "; } }}// Function to remove subtreesnode* pruneTree(node* root){ // Base Case if (!root) { return NULL; } // Search for required condition // in left and right half root->left = pruneTree(root->left); root->right = pruneTree(root->right); // If the node is even // and leaf node if (root->data % 2 == 0 && !root->right && !root->left) return NULL; return root;}// Driver Codeint main(){ struct node* root = newNode(1); root->left = newNode(2); root->left->left = newNode(8); root->left->right = newNode(10); root->right = newNode(7); root->right->left = newNode(12); root->right->right = newNode(5); // Function Call node* newRoot = pruneTree(root); // Print answer printLevelOrder(newRoot); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Node of the treestatic class node { int data; node left, right;};// Function to create a new nodestatic node newNode(int key){ node temp = new node(); temp.data = key; temp.left = temp.right = null; return (temp);}// Function to print tree level wisestatic void printLevelOrder(node root){ // Base Case if (root==null) return; // Create an empty queue for // level order traversal Queue<node> q = new LinkedList<>(); // Enqueue Root q.add(root); while (!q.isEmpty()) { // Print front of queue and // remove it from queue node temp = q.peek(); System.out.print(temp.data+ " "); q.remove(); // If left child is present if (temp.left != null) { q.add(temp.left); } // Otherwise else if (temp.right != null) { System.out.print("null "); } // If right child is present if (temp.right != null) { q.add(temp.right); } // Otherwise else if (temp.left != null) { System.out.print("null "); } }}// Function to remove subtreesstatic node pruneTree(node root){ // Base Case if (root == null) { return null; } // Search for required condition // in left and right half root.left = pruneTree(root.left); root.right = pruneTree(root.right); // If the node is even // and leaf node if (root.data % 2 == 0 && root.right==null && root.left==null) return null; return root;}// Driver Codepublic static void main(String[] args){ node root = newNode(1); root.left = newNode(2); root.left.left = newNode(8); root.left.right = newNode(10); root.right = newNode(7); root.right.left = newNode(12); root.right.right = newNode(5); // Function Call node newRoot = pruneTree(root); // Print answer printLevelOrder(newRoot);}}// This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approach# Node of the treeclass node: def __init__(self,data): self.data = data self.left = None self.right = None# Function to print tree level wisedef printLevelOrder(root): # Base Case if (root==None): return # Create an empty queue for # level order traversal q = [] # Enqueue Root q.append(root) while(len(q)>0): # Print front of queue and # remove it from queue temp = q[0] print(temp.data,end = " ") q = q[1:] # If left child is present if (temp.left != None): q.append(temp.left) # Otherwise elif (temp.right != None): print("NULL",end= " ") # If right child is present if (temp.right != None): q.append(temp.right) # Otherwise elif (temp.left != None): print("NULL",end = " ")# Function to remove subtreesdef pruneTree(root): # Base Case if (root==None): return None # Search for required condition # in left and right half root.left = pruneTree(root.left) root.right = pruneTree(root.right) # If the node is even # and leaf node if (root.data % 2 == 0 and root.right == None and root.left==None): return None return root# Driver Codeif __name__ == '__main__': root = node(1) root.left = node(2) root.left.left = node(8) root.left.right = node(10) root.right = node(7) root.right.left = node(12) root.right.right = node(5) # Function Call newRoot = pruneTree(root) # Print answer printLevelOrder(newRoot) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Node of the treeclass node { public int data; public node left, right;};// Function to create a new nodestatic node newNode(int key){ node temp = new node(); temp.data = key; temp.left = temp.right = null; return (temp);}// Function to print tree level wisestatic void printLevelOrder(node root){ // Base Case if (root == null) return; // Create an empty queue for // level order traversal Queue<node> q = new Queue<node>(); // Enqueue Root q.Enqueue(root); while (q.Count != 0) { // Print front of queue and // remove it from queue node temp = q.Peek(); Console.Write(temp.data+ " "); q.Dequeue(); // If left child is present if (temp.left != null) { q.Enqueue(temp.left); } // Otherwise else if (temp.right != null) { Console.Write("null "); } // If right child is present if (temp.right != null) { q.Enqueue(temp.right); } // Otherwise else if (temp.left != null) { Console.Write("null "); } }}// Function to remove subtreesstatic node pruneTree(node root){ // Base Case if (root == null) { return null; } // Search for required condition // in left and right half root.left = pruneTree(root.left); root.right = pruneTree(root.right); // If the node is even // and leaf node if (root.data % 2 == 0 && root.right==null && root.left==null) return null; return root;}// Driver Codepublic static void Main(String[] args){ node root = newNode(1); root.left = newNode(2); root.left.left = newNode(8); root.left.right = newNode(10); root.right = newNode(7); root.right.left = newNode(12); root.right.right = newNode(5); // Function Call node newRoot = pruneTree(root); // Print answer printLevelOrder(newRoot);}}// This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach // Node of the tree class node { constructor(key) { this.left = null; this.right = null; this.data = key; } } // Function to create a new node function newNode(key) { let temp = new node(key); return (temp); } // Function to print tree level wise function printLevelOrder(root) { // Base Case if (root == null) return; // Create an empty queue for // level order traversal let q = []; // Enqueue Root q.push(root); while (q.length != 0) { // Print front of queue and // remove it from queue let temp = q[0]; document.write(temp.data+ " "); q.shift(); // If left child is present if (temp.left != null) { q.push(temp.left); } // Otherwise else if (temp.right != null) { document.write("Null "); } // If right child is present if (temp.right != null) { q.push(temp.right); } // Otherwise else if (temp.left != null) { document.write("Null "); } } } // Function to remove subtrees function pruneTree(root) { // Base Case if (root == null) { return null; } // Search for required condition // in left and right half root.left = pruneTree(root.left); root.right = pruneTree(root.right); // If the node is even // and leaf node if (root.data % 2 == 0 && root.right==null && root.left==null) return null; return root; } let root = newNode(1); root.left = newNode(2); root.left.left = newNode(8); root.left.right = newNode(10); root.right = newNode(7); root.right.left = newNode(12); root.right.right = newNode(5); // Function Call let newRoot = pruneTree(root); // Print answer printLevelOrder(newRoot); // This code is contributed by decode2207.</script> |
Output:
1 NULL 7 NULL 5
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
