How to find largest common sub-tree in the given two binary search trees?

Posted by Bhushan on Stack Overflow See other posts from Stack Overflow or by Bhushan
Published on 2011-07-13T04:11:11Z Indexed on 2012/04/06 23:30 UTC
Read the original article Hit count: 258

Two BSTs (Binary Search Trees) are given. How to find largest common sub-tree in the given two binary trees?

EDIT 1: Here is what I have thought:

Let, r1 = current node of 1st tree r2 = current node of 2nd tree

There are some of the cases I think we need to consider:

Case 1 : r1.data < r2.data
     2 subproblems to solve:
     first, check r1 and r2.left 
     second, check r1.right and r2

Case 2 : r1.data > r2.data
     2 subproblems to solve:
       - first, check r1.left and r2
       - second, check r1 and r2.right

Case 3 : r1.data == r2.data
     Again, 2 cases to consider here:
     (a) current node is part of largest common BST
         compute common subtree size rooted at r1 and r2
     (b)current node is NOT part of largest common BST
         2 subproblems to solve:
         first, solve r1.left and r2.left 
         second, solve r1.right and r2.right

I can think of the cases we need to check, but I am not able to code it, as of now. And it is NOT a homework problem. Does it look like?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about tree