Least common ancestor search in binary tree non recursive version - Java

Question

I am searching a non recursive algorithm version of finding the least common ancestor in a sorted binary tree written in Java. Everything I found is only the recursive version (even on stackoverflow and on other websites).

Can some one write or direct me to the non recursive version (using while loop)? Also write if this version is more efficient in terms of time complexity?

Answer 1

Just happened to see this long forgotten question.

Do you mean something like, if you are given a tree:

       A
   B       C
 D   E   F   G
H I J K L M N O

commonAncestor(L,G) = C
commonAncestor(H,O) = A
commonAncestor(B,H) = B

something like that?

2 methods to give (all assume the provided nodes are in the tree):

If there are link to parent (i.e. you are pointing from B back to A), then solution is easy, similar to finding intersecting linked list:

find depth of Node1 and Node2, assuming the depth is D1 and D2. Find the difference between D1 and D2 (assuming d). Have pointer to Node1 and Node2 (assume p1 and p2). For the node with higher depth, navigate to parent d-th times. At this point, p1 and p2 will have same depth beneath the ancestor. Just have a simple loop to navigate both p1 and p2 to parent, until you hit the node that p1 == p2.

---

If no parent link in node, you can iteratively navigate the tree:

currentNode = root;
while (true) {
    if (currentNode == node1 
            || currentNode == node2 
            || (currentNode > node1) != (currentNode > node2) ) {
        break;  // current node is the common ancestor, as node1 and node2 
                // will go to different sub-tree, or we actually 
                // found node1/2 and the other node is its child
    } else if (currentNode > node1) {
        currentNode = currentNode.left;
    } else { // currentNode < node1/2
        currentNode = currentNode.right;
    }
}

// currentNode will be the answer you want

The basic idea is, given it is a binary search tree, if two nodes are both larger / smaller than current node, it will goes to same child tree. So the common ancestor is the node that two values goes to different children, i.e. when one is smaller than current node and the other one is larger.