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;

}