Check for Same BSTs from Arrays: GeeksforGeeks

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:

Advertisements

Tagged: , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: