Posts
No more heatmaps that are just population maps!
-
I'm pleased to announce that there's a brand new 0.50 version of the DSTK out! It has a lot of bug fixes, and a couple of major new features, and you can get...
44 seconds ago
Assumptions: nodes "a" and "b" are not repeated into the tree and exist.
ReplyDeleteBinary tree:
public static Node lca(Node n, Node a, Node b) {
if (n == null) return null;
if (n == a || n == b) return n;
Node l = lca(n.left, a, b);
Node r = lca(n.right, a, b);
if (l != null && r != null) {
return n;
} else {
if (l != null) {
return l;
} else {
return r;
}
}
For a BST:
public static Node lca(Node n, Node a, Node b) {
if (n == null) return null;
if (min(a,b) <= n.value && n.value <= max(a,b)) return n;
if (n.value < min(a, b)) return lca(n.right, a, b);
if (n.value > max(a, b)) return lca(n.left, a, b);
return null;
}