BST Intersection :
Difficulty Level : Medium
Submissions : 167
Asked In :
Marks :10
: 2 | : 0
Given the inorder traversals of $$$2$$$ binary search trees, find their intersection.
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 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.
5 3 1 2 3 4 5 1 3 4
3 1 3 4
