Binary Search Trees: Given 2 BST, check if it has same set of elements or not

Problem Statement:

You are given 2 BST.

You need to check if 2 BST has same set of elements or not

Structure of 2 BST can be different

BST is a tree that satisfies below condition:

1. Left subtree will have the node less than the node key

2. Right subtree will have the node greater than the node key

3. Duplicate values are not allowed

Example:

Solution Explanation:

We will apply in-order traversal for both of the trees.

One in-order traversal is applied on the trees, it will generated sorted array.

Then check if both the array are same.

InOrder traversal : Left -> Root -> Right

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include<iostream> 
#include<vector> 

using namespace std;

class Node {
public:
    int data;
    Node* left, *right;
    Node (int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};



void solution(Node *root, vector<int> &arr)
{
    if (root == NULL) 
    return;
    
    solution(root->left, arr);
    arr.push_back(root->data);
    solution(root->right, arr);	
}

bool checkTwoBST(Node* tree1, Node* tree2) 
{
    
    vector<int> arr1, arr2;

    solution(tree1, arr1);
    solution(tree2, arr2);
    
    if (arr1.size() != arr2.size())
        return false;
        
    for (int i=0; i<arr1.size(); i++) {
        
        if (arr1[i] != arr2[i]) 
            return false;
    }
    
    return true;
}


int main() {
    
    // Tree 1
    //         25
    //        /  \
    //      20    30
    //     /  \     \
    //    15  22    35
    Node* root1 = new Node(25);
    root1->left = new Node(20);
    root1->right = new Node(30);
    root1->left->left = new Node(15);
    root1->left->right = new Node(22);
    root1->right->right = new Node(35);
    
    // Tree 2
    //         25
    //        /  \
    //      22    30
    //     /       \
    //    15        35
    //     \
    //     20
    Node* root2 = new Node(25);
    root2->left = new Node(22);
    root2->right = new Node(30);
    root2->left->left = new Node(15);
    root2->left->left->right = new Node(20);
    root2->right->right = new Node(35);
    
    if (checkTwoBST(root1, root2)) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
    
    return 0;
}

Output

True