Check for Identical BSTs without building the trees | GeeksforGeeks
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.
Check if stream is finished if yes -> return false
Check if both the stream has same number of elements, if not -> return false
Check if root is same, if not -> return false
leftsubtree arrays = constructed from smaller elements than root
rightsubtree arrays = constructed from greater elements than root
if leftsubtree == rightsubtree -> return true
For finding result in step 6, follow above steps recursively
def checkidenticaltree(a, b):
if len(a) != len(b):
return False
if a[0] != b[0]:
return False
if len(a) <= 1:
return True
a_left = []
a_right = []
for x in a:
if x < a[0]:
a_left.append(x)
elif x > a[0]:
a_right.append(x)
b_left = []
b_right = []
for x in b:
if x < b[0]:
b_left.append(x)
elif x > b[0]:
b_right.append(x)
return checkidenticaltree(a_right, b_right) and checkidenticaltree(a_left, b_left)
The idea is to check of if next smaller and greater elements are same in both arrays. Same properties are recursively checked for left and right subtrees. The idea looks simple, but implementation requires checking all conditions for all element.
https://gist.github.com/KodeSeeker/9859330
http://algorithms.tutorialhorizon.com/check-if-two-bsts-are-identical/
public boolean identicalBSTs(Node rootA, Node rootB){
if((rootA==null)&&(rootB==null)){
return true;
}else if((rootA!=null && rootB==null)||(rootA==null && rootB!=null)){
return false;
}else if(rootA.data==rootB.data){
return identicalBSTs(rootA.left, rootB.left) && identicalBSTs(rootA.right, rootB.right);
}else{
return false;
}
}
http://stackoverflow.com/questions/10951927/identical-bsts
Read full article from Check for Identical BSTs without building the trees | GeeksforGeeks
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.
a[] = {2, 4, 1, 3} will construct following tree.
2
/ \
1 4
/
3
b[] = {2, 4, 3, 1} will also also construct the same tree.
2
/ \
1 4
/
3
So the output is "True"
就是把这个数组里面的元素一个一个地插入到一个初始为空的BST里面,后面的便是利用BST的特性和递归的思想了.Alternative Solution from http://tech-queries.blogspot.com/2011/06/check-if-identical-bsts-from-given.htmlCheck if stream is finished if yes -> return false
Check if both the stream has same number of elements, if not -> return false
Check if root is same, if not -> return false
leftsubtree arrays = constructed from smaller elements than root
rightsubtree arrays = constructed from greater elements than root
if leftsubtree == rightsubtree -> return true
For finding result in step 6, follow above steps recursively
def checkidenticaltree(a, b):
if len(a) != len(b):
return False
if a[0] != b[0]:
return False
if len(a) <= 1:
return True
a_left = []
a_right = []
for x in a:
if x < a[0]:
a_left.append(x)
elif x > a[0]:
a_right.append(x)
b_left = []
b_right = []
for x in b:
if x < b[0]:
b_left.append(x)
elif x > b[0]:
b_right.append(x)
return checkidenticaltree(a_right, b_right) and checkidenticaltree(a_left, b_left)
According to BST property, elements of left subtree must be smaller and elements of right subtree must be greater than root.
Two arrays represent sane BST if for every element x, the elements in left and right subtrees of x appear after it in both arrays. And same is true for roots of left and right subtrees.
/* The main function that checks if two arrays a[] and b[] of size n construct same BST. The two values 'min' and 'max' decide whether the call is made for left subtree or right subtree of a parent element. The indexes i1 and i2 are the indexes in (a[] and b[]) after which we search the left or right child. Initially, the call is made for INT_MIN and INT_MAX as 'min' and 'max' respectively, because root has no parent. i1 and i2 are just after the indexes of the parent element in a[] and b[]. */bool isSameBSTUtil(int a[], int b[], int n, int i1, int i2, int min, int max){ int j, k; /* Search for a value satisfying the constraints of min and max in a[] and b[]. If the parent element is a leaf node then there must be some elements in a[] and b[] satisfying constraint. */ for (j=i1; j<n; j++) if (a[j]>min && a[j]<max) break; for (k=i2; k<n; k++) if (b[k]>min && b[k]<max) break; /* If the parent element is leaf in both arrays */ if (j==n && k==n) return true; /* Return false if any of the following is true a) If the parent element is leaf in one array, but non-leaf in other. b) The elements satisfying constraints are not same. We either search for left child or right child of the parent element (decinded by min and max values). The child found must be same in both arrays */ if (((j==n)^(k==n)) || a[j]!=b[k]) return false; /* Make the current child as parent and recursively check for left and right subtrees of it. Note that we can also pass a[k] in place of a[j] as they are both are same */ return isSameBSTUtil(a, b, n, j+1, k+1, a[j], max) && // Right Subtree isSameBSTUtil(a, b, n, j+1, k+1, min, a[j]); // Left Subtree}// A wrapper over isSameBSTUtil()bool isSameBST(int a[], int b[], int n){ return isSameBSTUtil(a, b, n, 0, 0, INT_MIN, INT_MAX);}
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.
public static boolean calculate(int []a, int []b){
return calculateRecursive(a, b, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private static boolean calculateRecursive(int []a,int []b, int i_a, int j_b, int min, int max){
int i;
int j;
for(i=i_a;i<a.length;i++)
if(a[i]>min && a[i]<max) break;
for(j=j_b;j<b.length;j++)
if(b[j]>min && b[j]<max) break;
if(i==a.length && j==b.length) //if does not hit the break then i is now a.length
return true;
else if(i==a.length || j==b.length)
return false;
else
return a[i]==b[j] && calculateRecursive(a,b,i+1,j+1,min,a[i]) && calculateRecursive(a,b,i+1,j+1,a[i],max);
}
/**
* Inefficient implementation, but easy to understand
**/
public static boolean calculateSlow(int []a, int []b){
if(a.length==0 && b.length==0) return true;
else if(a.length==0 || b.length==0) return false;
else return a[0]==b[0]&&calculateSlow(getBiggerElements(a,a[0]),getBiggerElements(b,b[0]))&&calculateSlow(getSmallerElements(a,a[0]),getSmallerElements(b,b[0]));
}
private static int[] getBiggerElements(int []a,int n){
int count=0;
for(int e:a){
if(e>n) count++;
}
int []ret= new int[count];
int i=0;
for(int e:a){
if(e>n) ret[i++]=e;
}
return ret;
}
private static int[] getSmallerElements(int []a,int n){
int count=0;
for(int e:a){
if(e<n) count++;
}
int []ret= new int[count];
int i=0;
for(int e:a){
if(e<n) ret[i++]=e;
}
return ret;
}
boolean checkIfSameBSTs(ArrayList<Integer> listForTree1, ArrayList<Integer> listForTree2) { // both trees should have same size if (listForTree1.size() != listForTree2.size()) { return false; } // if both trees are null trees if (listForTree1.size() == 0) { return true; } // root node has to be the same if (listForTree1.get(0) == listForTree2.get(0)) { // segregate nodes for left and right sub-trees for both trees ArrayList<Integer> listForLeftTree1 = new ArrayList(); ArrayList<Integer> listForRightTree1 = new ArrayList(); ArrayList<Integer> listForLeftTree2 = new ArrayList(); ArrayList<Integer> listForRightTree2 = new ArrayList(); for (int i = 1; i < listForTree1.size(); i++) { if (listForTree1.get(i) < listForTree1.get(0)) { listForLeftTree1.add(listForTree1.get(i)); } else { listForRightTree1.add(listForTree1.get(i)); } if (listForTree2.get(i) < listForTree2.get(0)) { listForLeftTree2.add(listForTree2.get(i)); } else { listForRightTree2.add(listForTree2.get(i)); } } // and check that left and right sub-tree are also same return checkIfSameBSTs(listForLeftTree1, listForLeftTree2) && checkIfSameBSTs(listForRightTree1, listForRightTree2); } return false; }http://algorithms.tutorialhorizon.com/check-if-two-bsts-are-identical/
public boolean identicalBSTs(Node rootA, Node rootB){
if((rootA==null)&&(rootB==null)){
return true;
}else if((rootA!=null && rootB==null)||(rootA==null && rootB!=null)){
return false;
}else if(rootA.data==rootB.data){
return identicalBSTs(rootA.left, rootB.left) && identicalBSTs(rootA.right, rootB.right);
}else{
return false;
}
}
http://stackoverflow.com/questions/10951927/identical-bsts
This answers the question as originally phrased, that is after identity of trees in the sense of same structure and elements.
Comparing in-order (or any other) sequentialisation won't work: different trees have the same traversal. For example, the trees
have the same in-order traversal
a,b,c,d,e. You can use two (different) traversals and check whether they are the same, respectively.
The classic solution, however, is a recursive algorithm:
equal Leaf(x) Leaf(y) => x == y
| equal Node(x,l1,r1) Node(y,l2,r2) => x == y && equal(l1,l2) && equal(r1,r2)
| equal _ _ => false;
It performs tree traversals on both trees simultaneously and takes time Θ(n), n the maximum of the respective number of nodes.
Read full article from Check for Identical BSTs without building the trees | GeeksforGeeks
