tag:blogger.com,1999:blog-6314876008291942531.post263423248848671578..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Find the lowest common ancestorUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-44571051268039948602012-12-02T19:32:14.263-08:002012-12-02T19:32:14.263-08:00Assumptions: nodes "a" and "b"...Assumptions: nodes "a" and "b" are not repeated into the tree and exist.<br /><br />Binary tree:<br /><br />public static Node lca(Node n, Node a, Node b) {<br /><br />if (n == null) return null;<br /><br />if (n == a || n == b) return n;<br /><br />Node l = lca(n.left, a, b);<br />Node r = lca(n.right, a, b);<br /><br />if (l != null && r != null) {<br /> return n;<br />} else {<br /> if (l != null) { <br /> return l;<br /> } else { <br /> return r;<br />}<br /><br />}<br /><br /><br />For a BST:<br /><br />public static Node lca(Node n, Node a, Node b) {<br /><br /> if (n == null) return null;<br /> <br /> if (min(a,b) <= n.value && n.value <= max(a,b)) return n;<br /> if (n.value < min(a, b)) return lca(n.right, a, b);<br /> if (n.value > max(a, b)) return lca(n.left, a, b);<br /><br /> return null;<br />}<br />Claudio Corsihttps://www.blogger.com/profile/13435215356783747956noreply@blogger.com