Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Assumptions: nodes "a" and "b" are not repeated into the tree and exist.Binary 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;}
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;
}