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