CareerCup

Let us say the number of nodes in tree a is M and in b is N. In naive method, we can search each element of one tree in the other tree. Searching will cost M lg N (or simply O(nlgn) if M ~ N and then the tree matching will cost O(M) worst case till the nodes don't match any further. We keep track of the node from where the match started and the length of the longest common sub-tree discovered so far, and replace these variables if the next match is longer. Overall cost = O(M lg N) + O(M) = O(M lg N). If M ~ N, cost = O(nlgn).

Can we improve on this ? Let us think of the BSTs as sorted arrays (which we can obtain by an O(n) in-order traversal of the tree). Our problem is similar to finding the longest common substring of the two sorted arrays which takes an O(N+M) time. Once we find the longest substring, we need to re-construct the common substring tree O(lg N). Overall complexity = O(n) which seems to beat the other strategy.

EDIT: Thanks to das. The longest common substring in in-order traversal will need to be rechecked for whether the common sub-trees are isomorphic as well. If this check is performed constant number of times, our complexity will still be O(n) otherwise it be also become O(nlgn).

Always Pre order of a BST is unique. meaning given a pre order, only one BST can be constructed out of it.

Using the above fact.
derive pre orders of both the BSTs and find the longest common substring

Let me know if there are issues with this

Looks like a dynamic programming question, the way I was thinking is along these lines

The roots of the trees may be equal, less, greater between the two trees. Let's say one root is bigger, then either that tree's(bigger tree) left sub tree can be equal to the smaller tree or the smaller tree's right sub tree can be the larger tree.

So we check on both sub trees O(logn)
Step 1:
For example: to find the largest sub tree on the left side, we traverse through the larger root tree until we find an equality then if we find two nodes that are equal, we compare the rest of three for equality, else we keep traversing.

Finding if the rest of trees are equal is O(n) worst case

Similarly for the right sub tree,
Step 2:
If we DO find common subtrees, we return the largest one.


However, if we don't find any common sub trees we try the right and left children of the tree until we have found a solution or have tried all the possibilities.

Overall O(n^2 logn)

This is my first response, so I hope it makes sense.

hi..
we can find subarray using inorder traversals which will take O(n),
the prob is isomorphic trees right,
get the preorders of the sub trees and check whether preorders are also equal or not,
if they are equal, the two subtrees are equal..

// for simplify, I just return the largest common BST root and number of nodes
#include <iostream>

using namespace std;

class NodeType{
public:
NodeType(int v=0):val(v),left(NULL),right(NULL){}
int val;
NodeType* left;
NodeType* right;
};
void updateMax(int & max,NodeType** common,int temp,NodeType* result){
if(max<temp){
max=temp;
*common=result;
}
}
int maxCommonBST(NodeType* root1,NodeType* root2,int & max,NodeType** common){
if(root1==NULL || root2==NULL)return 0;
if(root1->val<root2->val){
/////////////////////////////////////
// root1 can be left child of root2
// or root2 can be right child of root1
maxCommonBST(root1,root2->left,max,common);
maxCommonBST(root1->right,root2,max,common);
return 0;
}
else if(root1->val>root2->val){
////////////////////////////////////
// root1 can be right child of root2
// or root2 can be left child of root1;
maxCommonBST(root1->left,root2,max,common);
maxCommonBST(root1,root2->right,max,common);
return 0;
}
else{
int left=maxCommonBST(root1->left,root2->left,max,common);
int right=maxCommonBST(root1->right,root2->right,max,common);
int total=left+1+right;
updateMax(max,common,total,root1);
return total;
}
}

int main(int argc,char* argv[]){
NodeType* root1=new NodeType(30);
root1->left=new NodeType(15);
root1->right=new NodeType(45);
root1->left->left=new NodeType(10);
root1->left->left->left=new NodeType(5);
root1->left->left->right=new NodeType(13);

NodeType*root2=new NodeType(30);
root2->left=new NodeType(10);
root2->left->left=new NodeType(5);
root2->left->right=new NodeType(13);

int max=0;
NodeType* com=NULL;
maxCommonBST(root1,root2,max,&com);

cout<<com->val<<" "<<max<<endl;
}

Can the root of the largest bst start at anynode?

First idea:
If the common bst has to start with the root of the smallest tree :

first put the biggest tree in A, and the other one in B.

maxLength = Integer.MIN_VALUE;
tree max;


Search in tree A the root of B. When you find it:
---- call a function that goes deep in A and check what's the match, storing the match in a temporary tree. if the length of the temporary tree is greater than maxLength then maxLength = temporary tree.length and max = temporary tree.

Keep searching in A the root of B until you finish seeing all the nodes in A.

At the end if the maxLength==Integer.MIN_VALUE return 0; else return maxLength!


Second idea:

Find the inorder traverse of A and B .. find the longest match between them.