Given a binary search tree of n nodes with distinct values. Also given are Q queries. Each query consists of a node value that has to be searched in the BST and skip the subtree that has given node as its root. If the provided node is the root itself then print “Empty” without quotes. After that print the preorder traversal of the BST.
Examples:
Input:
N = 7, Q = 2
BST elements: 8 4 10 15 14 88 64
Query1: 15
Query2: 88
Output: 8 4 10
8 4 10 15 14
The tree below will be formed from the elements given
8
/ \
4 10
\
15
/ \
14 88
/
64
Query1 = 15. So, skip the subtree with 15 as root.
The remaining tree is :
8
/ \
4 10
The preorder traversal of the above tree is: 8 4 10
Query2 = 88. So we skip the subtree with 88 as root.
The remaining tree is :
8
/ \
4 10
\
15
/
14
The preorder traversal of the above tree is: 8 4 10 15 14
A naive approach is to traverse the entire tree and store its pre-order traversal. In every query, perform a pre-order traversal treating node as root. Print the entire tree’s pre-order traversal except the elements that are in the pre-order traversal of the tree which treats node as the root.
An efficient approach is to store the entire pre-order traversal of the tree in a container. While finding the pre-order traversal of the tree, store the number of recursive calls from the node and store it in a hash-table(mp). This effectively stores the entire size of the subtree treating any node as the root. While performing every query, print the pre-order traversal of the tree, till the node is found, once it is found, perform a jump of mp[node] steps so that the subtree is skipped.
Below is the implementation of the above approach:
C++
// C++ program to insert nodes// and print the preorder traversal#include <bits/stdc++.h>using namespace std;// vector to store pre-ordervector<int> pre;// map to store the height// of every subtreeunordered_map<int, int> mp;// structure to store the BSTstruct Node { int data; Node* left = NULL; Node* right = NULL;};// locates the memory spaceNode* newNode(int key){ Node* temp = new Node; temp->data = key; temp->left = NULL; temp->right = NULL; return temp;}// inserts node in the BSTNode* insertNode(Node* head, int key){ // if first node if (head == NULL) head = newNode(key); else { // move to left if (key < head->data) head->left = insertNode(head->left, key); // move to right else head->right = insertNode(head->right, key); } return head;}// Function to compute the pre-order// and compute the height of every sub-treeint preOrder(Node* head){ // leaf node is null if (head == NULL) return 0; pre.push_back(head->data); mp[head->data] += preOrder(head->left); mp[head->data] += preOrder(head->right); mp[head->data] += 1; return mp[head->data];}// Function to perform every queriesvoid performQueries(int node){ // traverse in the pre-order // jump the subtree which has node for (int i = 0; i < pre.size();) { // jump the subtree which has the node if (pre[i] == node) { i += mp[pre[i]]; } // print the pre-order else { cout << pre[i] << " "; i++; } } cout << endl;}// Driver Codeint main(){ Node* root = NULL; /* 8 / \ 4 10 \ 15 / \ 14 88 / 64 */ root = insertNode(root, 8); root = insertNode(root, 4); root = insertNode(root, 10); root = insertNode(root, 15); root = insertNode(root, 14); root = insertNode(root, 88); root = insertNode(root, 64); // Pre-order traversal of tree preOrder(root); // Function call to perform queries performQueries(15); performQueries(88); return 0;} |
Java
// Java program to insert nodes// and print the preorder traversalimport java.util.*;class Node{ int data; Node left, right; Node(int key) { data = key; left = right = null; }}class GFG{ // ArrayList to // store pre-order static ArrayList<Integer> pre = new ArrayList<Integer>(); // map to store the height // of every subtree static HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); public static Node insertNode(Node head, int key){ // if first node if (head == null) head = new Node(key); else { // move to left if (key < head.data) head.left = insertNode(head.left, key); // move to right else head.right = insertNode(head.right, key); } return head;}public static int preOrder(Node head){ // leaf node is null if (head == null) return 0; pre.add(head.data); mp.put(head.data, head.data + preOrder(head.left)); mp.put(head.data, head.data + preOrder(head.right)); mp.put(head.data, head.data + 1); return mp.get(head.data);}// Function to perform // every queriespublic static void performQueries(int node){ // traverse in the pre-order // jump the subtree which has node for (int i = 0; i < pre.size();) { // jump the subtree // which has the node if (pre.get(i) == node) { i += mp.get(pre.get(i)); } // print the pre-order else { System.out.print(pre.get(i) + " "); i++; } } System.out.println();} public static void main (String[] args) { Node root = null;/* 8 / \ 4 10 \ 15 / \ 14 88 / 64 */root = insertNode(root, 8);root = insertNode(root, 4);root = insertNode(root, 10);root = insertNode(root, 15);root = insertNode(root, 14);root = insertNode(root, 88);root = insertNode(root, 64);// Pre-order traversal of treepreOrder(root);// Function call to // perform queriesperformQueries(15);performQueries(88); }} |
Python3
# Python3 program to insert nodes# and print the preorder traversalfrom typing import Dict# Vector to store pre-orderpre = []# Map to store the height# of every subtreemp: Dict[int, int] = dict()# Structure to store the BSTclass Node: def __init__(self, data: int) -> None: self.data = data self.left = None self.right = None# Inserts node in the BSTdef insertNode(head: Node, key: int) -> Node: # If first node if (head == None): head = Node(key) else: # Move to left if (key < head.data): head.left = insertNode(head.left, key) # Move to right else: head.right = insertNode(head.right, key) return head# Function to compute the pre-order# and compute the height of every sub-treedef preOrder(head: Node) -> int: global pre, mp # Leaf node is None if (head == None): return 0 pre.append(head.data) if head.data not in mp: mp[head.data] = 0 mp[head.data] += preOrder(head.left) mp[head.data] += preOrder(head.right) mp[head.data] += 1 return mp[head.data]# Function to perform every queriesdef performQueries(node: int) -> None: # Traverse in the pre-order # jump the subtree which has node i = 0 while i < len(pre): # Jump the subtree which has the node if (pre[i] == node): i += mp[pre[i]] # Print the pre-order else: print(pre[i], end = " ") i += 1 print()# Driver Codeif __name__ == "__main__": root = None ''' 8 / \ 4 10 \ 15 / \ 14 88 / 64 ''' root = insertNode(root, 8) root = insertNode(root, 4) root = insertNode(root, 10) root = insertNode(root, 15) root = insertNode(root, 14) root = insertNode(root, 88) root = insertNode(root, 64) # Pre-order traversal of tree preOrder(root) # Function call to perform queries performQueries(15) performQueries(88)# This code is contributed by sanjeev2552 |
C#
// C# program to insert nodes// and print the preorder traversalusing System;using System.Collections.Generic;class Node{ public int data; public Node left, right; public Node(int key) { data = key; left = right = null; }}class GFG{ // List to store pre-order static List<int> pre = new List<int>(); // map to store the height // of every subtree static Dictionary<int, int> mp = new Dictionary<int, int>(); public static Node insertNode(Node head, int key) { // if first node if (head == null) head = new Node(key); else { // move to left if (key < head.data) head.left = insertNode(head.left, key); // move to right else head.right = insertNode(head.right, key); } return head; } public static int preOrder(Node head) { // leaf node is null if (head == null) return 0; pre.Add(head.data); mp[head.data]= head.data + preOrder(head.left); mp[head.data]= head.data + preOrder(head.right); mp[head.data]= head.data + 1; return mp[head.data]; } // Function to perform every queries public static void performQueries(int node) { // traverse in the pre-order // jump the subtree which has node for (int i = 0; i < pre.Count;) { // jump the subtree // which has the node if (pre[i] == node) { i += mp[pre[i]]; } // print the pre-order else { Console.Write(pre[i] + " "); i++; } } Console.WriteLine(); } // Driver Code public static void Main(String[] args) { Node root = null; /* 8 / \ 4 10 \ 15 / \ 14 88 / 64 */ root = insertNode(root, 8); root = insertNode(root, 4); root = insertNode(root, 10); root = insertNode(root, 15); root = insertNode(root, 14); root = insertNode(root, 88); root = insertNode(root, 64); // Pre-order traversal of tree preOrder(root); // Function call to // perform queries performQueries(15); performQueries(88); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to insert nodes// and print the preorder traversalclass Node{ constructor(key) { this.data = key; this.left = null; this.right = null; }}// List to store pre-ordervar pre = [];// map to store the height// of every subtreevar mp = new Map(); function insertNode(head, key){ // If first node if (head == null) head = new Node(key); else { // Move to left if (key < head.data) head.left = insertNode( head.left, key); // Move to right else head.right = insertNode( head.right, key); } return head;}function preOrder(head){ // Leaf node is null if (head == null) return 0; pre.push(head.data); mp.set(head.data, head.data + preOrder(head.left)); mp.set(head.data, head.data + preOrder(head.right)); mp.set(head.data, mp.get(head.data) + 1); return mp.get(head.data);}// Function to perform every queriesfunction performQueries(node){ // Traverse in the pre-order // jump the subtree which has node for(var i = 0; i < pre.length;) { // Jump the subtree // which has the node if (pre[i] == node) { i += mp.get(pre[i]); } // Print the pre-order else { document.write(pre[i] + " "); i++; } } document.write("<br>");} // Driver Codevar root = null;/* 8 / \ 4 10 \ 15 / \ 14 88 / 64 */root = insertNode(root, 8);root = insertNode(root, 4);root = insertNode(root, 10);root = insertNode(root, 15);root = insertNode(root, 14);root = insertNode(root, 88);root = insertNode(root, 64);// Pre-order traversal of treepreOrder(root);// Function call to // perform queriesperformQueries(15);performQueries(88); // This code is contributed by rutvik_56</script> |
Output
8 4 10 8 4 10 15 14
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
