700. Remove nodes from Binary Search Tree
0
Medium
Given an array A1 of integers, you need to construct a Binary Search Tree (BST) using the elements of A1. Then, you are given another array A2. Your task is to delete each node from the BST that is present in A2. Finally, print the preorder traversal of the resulting tree. It is guaranteed that the elements of A2 will be present in the tree.
Note: If a node has two children, consider its inorder successor as its replacement.
Note: If a node has two children, consider its inorder successor as its replacement.
Input Format
The first line contains an integer t, which represents the number of test cases.
Each test case consists of four lines. The first line contains an integer n, which represents the length of array A1. The next line contains n space-separated integers denoting the elements of A1. Similarly, the third line contains an integer m, which represents the length of array A2. The next line contains m space-separated integers denoting the elements of A2.
Each test case consists of four lines. The first line contains an integer n, which represents the length of array A1. The next line contains n space-separated integers denoting the elements of A1. Similarly, the third line contains an integer m, which represents the length of array A2. The next line contains m space-separated integers denoting the elements of A2.
Output Format
Print the preorder traversal of the final resultant tree.
Example
Input
1
7
5 3 2 4 7 6 8
3
2 3 5
Output
6 4 7 8
Constraints
1 < t < 100
1< n,m < 1000
1< n,m < 1000
Loading...
View Submissions
Console