tag:blogger.com,1999:blog-6294663875929591018.post5137470644752616541..comments2023-09-24T03:12:58.137-07:00Comments on Ramblings of a techie: Find common parent in a binary search tree in JavaBragBoyhttp://www.blogger.com/profile/01173019524783723568noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6294663875929591018.post-18416835526566982502011-02-20T21:28:25.393-08:002011-02-20T21:28:25.393-08:00http://www.sureinterview.com/shwqst/114001
Genera...http://www.sureinterview.com/shwqst/114001<br /><br />General idea<br /><br />1. If the parent node link is given, we can trace each node back to the root. The problem is to check where those two links merge. 2. If it is a binary search tree (BST), we needs to find the node whose branch covers both nodes. Each node in BST has a min and a max that covers some certain range.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-43389962837166669242010-12-13T10:50:51.262-08:002010-12-13T10:50:51.262-08:00follow is is efficient one
while( root != null ){...follow is is efficient one<br /><br />while( root != null ){<br /> int value = root.getValue();<br /> if( value > value1 && value > value2 ){<br /> root = root.getLeft();<br /> } else if( value < value1 && value < value2 ){<br /> root = root.getRight();<br /> } else {<br /> return root;<br /> }<br /> }<br /><br /> return null; // only if empty treeMaulish Sonihttps://www.blogger.com/profile/06269032333519687672noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-25506695145237739772010-02-21T22:47:37.112-08:002010-02-21T22:47:37.112-08:00@Mavi: What you say is correct. As a matter of fac...@Mavi: What you say is correct. As a matter of fact, I have an implementation for this problem <a href="http://www.technicalypto.com/2010/02/least-common-ancestor-without-using.html" rel="nofollow">without having an ancestor node</a>.BragBoyhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-74864260896033666912010-02-21T13:08:09.902-08:002010-02-21T13:08:09.902-08:00this solution actually has problems. If the nodes ...this solution actually has problems. If the nodes have only the left and right pointers rather than the ancestor pointer the solution tends to fail. Because in that case a bottom up manner will not work, since the pointers can only show the nodes which are left of the current and right of the current one. <br />Moreover how can you do if at the beginning of the question you only have the node values, but not the positions ? You'll need to track down to find where they are and spent 2 passes to find their exact locations. Only after then you may try to find the common ancestor but with down-pointing pointers it is harder than this implementation. Nice work though :)Mavi Domateshttps://www.blogger.com/profile/08203794186682741745noreply@blogger.com