Thursday, November 29, 2012

Find the lowest common ancestor

For a binary tree for a binary search tree

1 comment:

  1. 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;
    }

    ReplyDelete