AlgoUniversity
  • Go Back
Discussion
BST Intersection :

Author

Ayush Kumar Shaw

Difficulty Level : Medium

Submissions : 167

Asked In : Amazon

Marks :10

: 2 | : 0

Given the inorder traversals of $$$2$$$ binary search trees, find their intersection.

Input

The first line contains $$$2$$$ integers $$$n,m(1 \leq n,m \leq 10^5)$$$ - the number of nodes in the first and second binary tree respectively.

The next line contains $$$n$$$ integers - $$$a_1,a_2,a_3,...,a_n(1 \leq a_i \leq 10^9)$$$ the inorder traversal of the first binary search tree.

The next line contains $$$n$$$ integers - $$$b_1,b_2,b_3,...,b_m(1 \leq b_i \leq 10^9)$$$ the inorder traversal of the second binary search tree.

Output

Output a single integer $$$k$$$ - the number of nodes common in both the binary search trees. In the next line output $$$k$$$ space separated integers $$$c1_c2,...,c_k$$$ - the nodes in the intersection of the $$$2$$$ BSTs sorted in increasing order.

Example

Input
5 3
1 2 3 4 5
1 3 4
Output
3
1 3 4 

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.