Binary Search Trees: Given 2 BST, print common nodes in the BST

Problem Statement:

Given 2 BST, print common nodes in the BST

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */


    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

Output:

2 8 9 10 11 12 14 

Solution Explanation:

Add both the tree elements into the vector.

Then check which elements are same and print the same.

Time Complexity: O(M + N)
Space Complexity: O(M + N)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Tree_Node 
{
public:
	int data;
	Tree_Node* left;
	Tree_Node* right;

	Tree_Node(int x) 
	{
		data = x;
		left = nullptr;
		right = nullptr;
	}
};

void inorderTraversal(Tree_Node* root, vector<int>& values)
{
    if (!root)
        return;
    inorderTraversal(root->left, values);
    values.push_back(root->data);
    inorderTraversal(root->right, values);
}

void solution(Tree_Node* root1, Tree_Node* root2) 
{
    
    vector<int> arr1, arr2;
    inorderTraversal(root1, arr1);
    inorderTraversal(root2, arr2);

    int i = 0;
    int j = 0;

    while(i < arr1.size() && j < arr2.size())
    {
        if(arr1[i] == arr2[j])
        {
            cout << arr1[i] << " ";
            i++;
            j++;
        }
        else if(arr1[i] < arr2[j])
        {
            i++;
        }
        else
        {
            j++;
        }
    }

}


int main()
{

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    Tree_Node* root = new Tree_Node(10);
    root->left = new Tree_Node(8);
    root->right = new Tree_Node(12);
    root->left->left = new Tree_Node(2);
    root->left->right = new Tree_Node(9);
    root->right->left = new Tree_Node(11);
    root->right->right = new Tree_Node(14);

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    Tree_Node* root_2 = new Tree_Node(10);
    root_2->left = new Tree_Node(8);
    root_2->right = new Tree_Node(12);
    root_2->left->left = new Tree_Node(2);
    root_2->left->right = new Tree_Node(9);
    root_2->right->left = new Tree_Node(11);
    root_2->right->right = new Tree_Node(14);

    solution(root, root_2);

    return 0;
}

Output

2 8 9 10 11 12 14