**Problem link:** http://www.geeksforgeeks.org/check-for-identical-bsts-without-building-the-trees/

**Problem Statement:**

Given two arrays which represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to tell whether two BSTs will be identical or not without actually constructing the tree.

For example, the input arrays are {2, 4, 3, 1} and {2, 1, 4, 3} will construct the same tree

**Solution Idea:**

By the definition of BST, all nodes in the left sub-tree is smaller than the root, and all elements of the right sub-tree is greater than the root. So, 2 arrays will construct the same BST if the 1st element of both arrays are the same, and this is recursively true for elements smaller than the 1st element for both arrays and also for elements bigger than the 1st element for both arrays. One thing to remember that when constructing these small arrays (smaller and bigger elements) you should preserve the original order of the elements. Take a look at `calculateSlow` function for this implementation.

Now, this algorithm can be improved without constructing the sub-arrays. The details can be found in the original link.

**Solution Gist:**

### Like this:

Like Loading...

*Related*

Tagged: array, binary-search-tree, binary-tree, hard, java, recursion, tree

## Leave a Reply