BST of two unsorted arrays

Question

This question was asked in an interview: Given two unsorted arrays, check if it will create the same bst. for example: 2, 1, 4, 0, and 2, 1, 0, 4 will be the same BST.

2 / \ 1 4 / 0 

suggest some useful algorithms.

Answer 1

• Take the first element - this will be the root (in the above case it is 2)
• All elements that are smaller than the root element should be displayed in the same order in both arrays.
  • In the above example, 0 and 1 are elements smaller than the root elements.
  • In the first array, the order is 1, 0
  • The same order is stored in the second array. Thus, both forms form the same structure.

• All elements that are larger than the root element should be displayed in the same order as in arrays.

  • In the above example, 4 is the only element larger than 2. It appears in both arrays. And so both arrays create BSTs that are structurally the same.

• And, of course, the very first condition is that both arrays must contain the same elements, but in a different order.

Therefore, this can be solved in linear time.

The pseudocode will look like this:

 int GetNextIncresingElement(int[] arr, ref int index, int root) { for(int i = index; i< arr.Length; i++) { if(arr[i] > root) { index = i; return arr[i]; } } return -1; } int GetNextDecreasingElement(int[] arr, ref int index, int root) { for(int i = index; i< arr.Length; i++) { if(arr[i] <= root) { index = i; return arr[i]; } } return -1; } bool CheckFormsSameBST(int[] arr1, int[] arr2) { int index1 = 1; int index2 = 1; int num1; int num2; int root = arr1[0]; if(root != arr2[0]) return false; while(true) { num1 = GetNextIncresingElement(arr1, ref index1, root); num2 = GetNextIncresingElement(arr2, ref index2, root); if(num1 != num2) return false; else { if(num1 == -1) break; } index1++; index2++; } index1 = 1; index2 = 1; while(true) { num1 = GetNextDecreasingElement(arr1, ref index1, root); num2 = GetNextDecreasingElement(arr2, ref index2, root); if(num1 != num2) return false; else { if(num1 == -1) break; } index1++; index2++; } return true; } 

Answer 2

I agree with the idea described by Peter and Algorist. But I believe that the subelements of each node (represented by an array smaller than this node and an array exceeding it) should also be considered in the same way. For example, 621407 and 621047 give the same BST, but 624017 do not. A function can be written recursively.

code example added:

 bool sameBST(int * t1, int * t2, int startPos, int endPos) { int rootPos1, rootPos2; if (endPos-startPos<0) return true; if (t1[startPos]!=t2[startPos]) return false; rootPos1=partition(t1,startPos,endPos,t1[startPos]); rootPos2=partition(t2,startPos,endPos,t2[startPos]); if (rootPos1!=rootPos2) return false; return sameBST(t1,t2,startPos,rootPos1-1) && sameBST(t1,t2,rootPos1+1,endPos); } 

The function section is the same as that you use in quicksort. Apparently, T (n) = 2T (n / 2) + O (n), which leads to the time complexity T (n) = O (nlogn). Due to recursion, the complexity of the space is O (logn)

Answer 3

You can check the detailed explanation of comparing two binary trees (not just BST) at Determine if two binary trees are equal . It is easy to create a BST from arrays, and then run the algorithm on these issues.

Answer 4

IMO, you can sort one array and perform a binary search from the second array into a sorted array, in the meantime, make sure you use each element. It will cost you mlogn.

Answer 5

check if it will create the same bst?

Yes.

start using the first element as root and save a number that is larger than the root on the right and less than the root on the left.

if you follow the above procedure, you will see that both trees are identical.

Answer 6

The point may be a comparison of the permutations of the sub-segments of one array with the corresponding sub-segments of another array (the order of the level of thinking):

starting from the first element in the array, for i = 0 for some n, the group of elements in the sets 2 ^ i

2 ^ 0 = 1: the first element is the root - both arrays should begin: [50].

2 ^ 1 = 2: any permutation of the following 2 elements in order:

 [25,75] or [75,25] 

2 ^ 2 = 4: any permutation of the following 4 elements in order:

 [10, 35, 60, 85] or [60, 35, 10, 85] or ... 

2 ^ 3 = 8: any permutation of the following 8 elements in order:

  [5, 16, 30, 40, …. 

so until 2 ^ n until the arrays are empty. corresponding sub-segments must have the same number of elements.

Answer 7

1) Sort the array using counting or numbering sorting.

2) Create a tree using our sorted array and the specified unsorted array (to check the insertion order). It will preserve the structure of the tree.

3) Compare both trees.

Everything can be done in linear time - O (n).

the code:

 import java.util.Arrays; public class BSTFromUnsorted { static class Node{ int key; int arrivalTime,min,max,root; Node left; Node right; Node(int k,int at){ key=k;left=null;right=null;arrivalTime=at; } } public static void printTree(Node n){ if(n==null) return; System.out.println(n.key+" "+ ((n.left!=null)?n.left.key:"-") + " " + ((n.right!=null)?n.right.key:"-") ); printTree(n.left); printTree(n.right); } public static boolean compareTree(Node n1,Node n2){ if(n1==null && n2==null) return true; return ( n1!=null && n2!=null && n1.key==n2.key && compareTree(n1.left,n2.left) && compareTree(n1.right,n2.right) ) ; } public static void main(String[] args){ int[] bstInsertOrder1={8, 10, 14, 3, 6, 4, 1, 7, 13}; int[] bstInsertOrder2={8, 3, 6, 1, 4, 7, 10, 14, 13}; Node n1 = buildBST(bstInsertOrder1); printTree(n1); System.out.println(); Node n2 = buildBST(bstInsertOrder2); printTree(n2); System.out.println("\nBoth are " + (compareTree(n1,n2)?"same":"different")); } public static Node buildBST(int[] insertOrder){ int length = insertOrder.length; Node[] sortedOrder = new Node[length]; for(int i=0;i<length;i++){ sortedOrder[i] = new Node(insertOrder[i],i); } Radix.radixsort(sortedOrder,length); int[] sortedIndex = new int[length]; for(int i=0;i<length;i++){ sortedOrder[i].max=sortedOrder[i].min=sortedOrder[i].root=i; sortedIndex[sortedOrder[i].arrivalTime]=i; } for (int i=length-1;i>0;i--){ int j = sortedIndex[i]; int min=sortedOrder[j].min-1,max=sortedOrder[j].max+1; Node n=null,n1; if(min>=0){ n = sortedOrder[sortedOrder[min].root]; } if(max<length){ n1=sortedOrder[sortedOrder[max].root]; if(n==null){ n=n1; } else{ n=(n.arrivalTime>n1.arrivalTime)?n:n1; } } n1=sortedOrder[j]; if(n.key<n1.key){ n.right=n1; n.max=n1.max; sortedOrder[n.max].root=sortedOrder[n.min].root; } else{ n.left=n1; n.min=n1.min; sortedOrder[n.min].root=sortedOrder[n.max].root; } } return sortedOrder[sortedIndex[0]]; } static class Radix { static int getMax(Node[] arr, int n) { int mx = arr[0].key; for (int i = 1; i < n; i++) if (arr[i].key > mx) mx = arr[i].key; return mx; } static void countSort(Node[] arr, int n, int exp) { Node output[] = new Node[n]; // output array int i; int count[] = new int[10]; Arrays.fill(count, 0); for (i = 0; i < n; i++) count[(arr[i].key / exp) % 10]++; for (i = 1; i < 10; i++) count[i] += count[i - 1]; for (i = n - 1; i >= 0; i--) { output[count[(arr[i].key / exp) % 10] - 1] = arr[i]; count[(arr[i].key / exp) % 10]--; } for (i = 0; i < n; i++) arr[i] = output[i]; } static void radixsort(Node[] arr, int n) { int m = getMax(arr, n); for (int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp); } } }