Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains 3 lines. The first line of each test case contains a string representing the tree as described below:
The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.
For example:
For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N
Note: Assume that all input BSTs are balanced.
The second line of test case holds an integer n denoting the number of nodes to be deleted. Finally, the last line of test case holds the n space-separated integer values to be deleted from the tree.
nput:
3
4 2 6 1 3 5 7
4
4 1 3 6
2 1 3 N N N 4
4
1 2 3 4
61 40 94 19 44 N 95
2
44 95
Output:
2 5 7
null
19 40 61 94
// { Driver Code Starts
//
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data, height;
Node *left, *right;
Node(int x)
{
data = x;
height = 1;
left = right = NULL;
}
};
int setHeights(Node* n)
{
if(!n) return 0;
n->height = 1 + max( setHeights(n->left) , setHeights(n->right) );
return n->height;
}
Node* buildTree(string str)
{
// Corner Case
if(str.length() == 0 || str[0] == 'N')
return NULL;
// Creating vector of strings from input
// string after spliting by space
vector<string> ip;
istringstream iss(str);
for(string str; iss >> str; )
ip.push_back(str);
// Create the root of the tree
Node* root = new Node(stoi(ip[0]));
// Push the root to the queue
queue<Node*> queue;
queue.push(root);
// Starting from the second element
int i = 1;
while(!queue.empty() && i < ip.size()) {
// Get and remove the front of the queue
Node* currNode = queue.front();
queue.pop();
// Get the current node's value from the string
string currVal = ip[i];
// If the left child is not null
if(currVal != "N") {
// Create the left child for the current node
currNode->left = new Node(stoi(currVal));
// Push it to the queue
queue.push(currNode->left);
}
// For the right child
i++;
if(i >= ip.size())
break;
currVal = ip[i];
// If the right child is not null
if(currVal != "N") {
// Create the right child for the current node
currNode->right = new Node(stoi(currVal));
// Push it to the queue
queue.push(currNode->right);
}
i++;
}
setHeights(root);
return root;
}
bool isBST(Node *n, int lower, int upper)
{
if(!n) return 1;
if( n->data <= lower || n->data >= upper ) return 0;
return isBST(n->left, lower, n->data) && isBST(n->right, n->data, upper) ;
}
pair<int,bool> isBalanced(Node* n)
{
if(!n) return pair<int,bool> (0,1);
pair<int,bool> l = isBalanced(n->left);
pair<int,bool> r = isBalanced(n->right);
if( abs(l.first - r.first) > 1 ) return pair<int,bool> (0,0);
return pair<int,bool> ( 1 + max(l.first , r.first) , l.second && r.second );
}
bool isBalancedBST(Node* root)
{
if( !isBST(root, INT_MIN, INT_MAX) )
cout<< "BST voilated, inorder traversal : ";
else if ( ! isBalanced(root).second )
cout<< "Unbalanced BST, inorder traversal : ";
else return 1;
return 0;
}
void printInorder(Node* n)
{
if(!n) return;
printInorder(n->left);
cout<< n->data << " ";
printInorder(n->right);
}
struct Node* deleteNode(struct Node* root, int data);
int main()
{
int t;
cin>>t;
getchar();
while(t--)
{
string s;
getline(cin,s);
Node* root = buildTree(s);
int n;
cin>> n;
int ip[n];
for(int i=0; i<n; i++)
cin>> ip[i];
for(int i=0; i<n; i++)
{
root = deleteNode(root, ip[i]);
if( !isBalancedBST(root) )
break;
}
if(root==NULL)
cout<<"null";
else
printInorder(root);
cout<< endl;
getline(cin,s); // to deal with newline char
}
return 1;
}
// } Driver Code Ends
/* Node is as follows:
struct Node
{
int data, height;
Node *left, *right;
Node(int x)
{
data = x;
height = 1;
left = right = NULL;
}
};
*/
void inordered(Node *root,vector<int> &v,int del)
{
if(root)
{
//call inordred function which sort number
//pushing only other than del element
inordered(root->left,v,del);
if(root->data!=del)
v.push_back(root->data);
inordered(root->right,v,del);
}
}
Node *BuildTree(vector<int> &v,int s,int e)
{
if(s>e)
return NULL ;
//mid value provide root of tree
int mid=(s+e)/2;
Node *root=new Node(v[mid]);
// now call left part of vector to build left subtree
root->left=BuildTree(v,s,mid-1);
//now call right part of vector to build right subtree
root->right=BuildTree(v,mid+1,e);
return root;
}
Node* deleteNode(Node* root, int data)
{
//add code here,
if(root==NULL)return NULL ;
vector<int> v;
//pushing all element execept equal to data element
inordered(root,v,data);
//Build Tree using sorted vector which easy to built it.
return BuildTree(v,0,v.size()-1);
}
