"Coding is just like talking to a unknown girl. Once you talked to her with guts, the next time you'll never afraid",Really? Yes , try it Now !!!
Everything here is for education and learning purpose only , individual holds rights on outer posts/links etc.
Team Cracking The Code
About Me
▼
Tuesday, July 26, 2011
Given two BST. Find maximum common BST. What Will Be Time Complexity can we do it in O(N) (TC for Checking Largest Commom BST) . What Will be Time Complexity if It will be the Binary Tree . Write an Efficient Algorithm
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
@anon yes i had similer approach in mind but due to lake of time wasen't able to put solution will look at code & then post itf will cover all the test cases
Without explanation why u post these type of questions? There lot of sites to do that,what is the use from your site? Here i see lot of questions are time inefficient and most of them are not solved
@Anon...Is its ur frustration or comment that u didn't get working code for this question ...but if u look at 450 problems out of 500+ u will each has efficient & working solution :) never mind , i will post soln of this as well ..but let me know how efficient u can think for this question ??
Let, r1 = current node of 1st tree r2 = current node of 2nd tree
ReplyDeleteThere 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
@anon yes i had similer approach in mind but due to lake of time wasen't able to put solution will look at code & then post itf will cover all the test cases
ReplyDeleteShashank :)
Without explanation why u post these type of questions? There lot of sites to do that,what is the use from your site? Here i see lot of questions are time inefficient and most of them are not solved
ReplyDelete@Anon...Is its ur frustration or comment that u didn't get working code for this question ...but if u look at 450 problems out of 500+ u will each has efficient & working solution :) never mind , i will post soln of this as well ..but let me know how efficient u can think for this question ??
ReplyDelete