Given two arrays which represents set of BST keys, check if they represents same BSTs or not. We are not allowed to build the tree.

For example, consider below arrays

X[] = { 15, 25, 20, 22, 30, 18, 10, 8, 9, 12, 6 }

Y[] = { 15, 10, 12, 8, 25, 30, 6, 20, 18, 9, 22 }

Both arrays represents same BSTs as shown below –

**C Implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <stdio.h> #include <stdlib.h> // Recursive function to check if X[0..n) and Y[0..n) represent same BSTs or not int isSameBST(int X[], int Y[], int n) { // take four auxiliary arrays of size n-1 each (as maximum keys in // left or right subtree can be n-1) int leftX[n-1], rightX[n-1], leftY[n-1], rightY[n-1]; int k = 0, l = 0, m = 0, o = 0; // if no element is present in the array, return true if (n == 0) return 1; // if 1st element differs in both array (root node key), return false if (X[0] != Y[0]) return 0; // if array contains only one key, return true if (n == 1) return 1; // process remaining keys and divide them into two groups for (int i = 1; i < n; i++) { // leftX[] will contain all elements less than X[0] if (X[i] < X[0]) leftX[k++] = X[i]; // rightX[] will contain all elements more than X[0] else rightX[l++] = X[i]; // leftY[] will contain all elements less than Y[0] if (Y[i] < Y[0]) leftY[m++] = Y[i]; // rightY[] will contain all elements more than Y[0] else rightY[o++] = Y[i]; } // return false if size of leftX[] & leftY[] differs i.e. // number of nodes in left subtree of both trees differs if (k != m) return 0; // return false if size of rightX[] & rightY[] differs i.e. // number of nodes in right subtree of both trees differs if (l != o) return 0; // check left subtree and right subtree return isSameBST(leftX, leftY, k) && isSameBST(rightX, rightY, l); } // Check if given keys represents same BSTs or not without building the BST int main(void) { int X[] = { 15, 25, 20, 22, 30, 18, 10, 8, 9, 12, 6 }; int Y[] = { 15, 10, 12, 8, 25, 30, 6, 20, 18, 9, 22 }; int n = sizeof(X) / sizeof(X[0]); int m = sizeof(Y) / sizeof(Y[0]); if (m == n && isSameBST(X, Y, n)) printf("Given keys represent same BSTs"); else printf("Given keys represent different BSTs"); return 0; } |

`Output:`

Given keys represent same BSTs

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n^{2}).

**Thanks for reading.**

Please use ideoneย orย C++ Shellย or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding ๐

## Leave a Reply

Line nos 37 and 38:

37: leftY[] will contain all elements less than

Y[0]38: if(Y[i] <

X[0])Thanks a lot for bringing this issue to our notice. Let us update the code. Happy coding ๐

I can solve the same problem by using map also right??

Abhsihyam, we don’t see how hashing solution is possible here. If you have anything in mind, do share with us. Thanks and Happy coding ๐

What would be the time complexity if given bsts are skewed tress?

Anuj, the time complexity is wrongly updated in the article. It should be O(n2). We will update the article. Thanks.

Intuitively I feel that the set of keys X equals set of keys Y iif they have the same BST. So just checking that the 2 arrays have the same key should determine if they yield the same BST.

What’s wrong with that approach?

Thanks for sharing your concern. Just checking that both arrays have same set of keys will not determine if they will yield the same BST as insertion order of keys is very important for BST structure. Two BSTs might have different structure if same keys are used but their insertion order is changed. For example, {1, 2, 3} and {2, 1, 3} will result in two separate BSTs. However, inorder traversal of both BST would be same.

Make sense, thanks!