[algorithm] How to find the lowest common ancestor of two nodes in any binary tree?

The Binary Tree here is may not necessarily be a Binary Search Tree.
The structure could be taken as -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

The maximum solution I could work out with a friend was something of this sort -
Consider this binary tree :

The inorder traversal yields - 8, 4, 9, 2, 5, 1, 6, 3, 7

And the postorder traversal yields - 8, 9, 4, 5, 2, 6, 7, 3, 1

So for instance, if we want to find the common ancestor of nodes 8 and 5, then we make a list of all the nodes which are between 8 and 5 in the inorder tree traversal, which in this case happens to be [4, 9, 2]. Then we check which node in this list appears last in the postorder traversal, which is 2. Hence the common ancestor for 8 and 5 is 2.

The complexity for this algorithm, I believe is O(n) (O(n) for inorder/postorder traversals, the rest of the steps again being O(n) since they are nothing more than simple iterations in arrays). But there is a strong chance that this is wrong. :-)

But this is a very crude approach, and I'm not sure if it breaks down for some case. Is there any other (possibly more optimal) solution to this problem?

Here is the C++ way of doing it. Have tried to keep the algorithm as much easy as possible to understand:

// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()`
class LowestCommonAncestor
{
  typedef char type;    
  // Data members which would behave as place holders
  const BinaryNode_t* m_pLCA;
  type m_Node1, m_Node2;

  static const unsigned int TOTAL_NODES = 2;

  // The core function which actually finds the LCA; It returns the number of nodes found
  // At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it!
  unsigned int Search (const BinaryNode_t* const pNode)
  {
    if(pNode == 0)
      return 0;

    unsigned int found = 0;

    found += (pNode->getData() == m_Node1);
    found += (pNode->getData() == m_Node2);

    found += Search(pNode->getLeft()); // below condition can be after this as well
    found += Search(pNode->getRight());

    if(found == TOTAL_NODES && m_pLCA == 0)
      m_pLCA = pNode;  // found !

    return found;
  }

public:
  // Interface method which will be called externally by the client
  const BinaryNode_t* Search (const BinaryNode_t* const pHead,
                              const type node1,
                              const type node2)
  {
    // Initialize the data members of the class
    m_Node1 = node1;
    m_Node2 = node2;
    m_pLCA = 0;

    // Find the LCA, populate to `m_pLCANode` and return
    (void) Search(pHead);
    return m_pLCA;
  }
};

How to use it:

LowestCommonAncestor lca;
BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith);
if(pNode != 0)
  ...

The lowest common ancestor between two nodes node1 and node2 is the lowest node in a tree that has both nodes as descendants.

The binary tree is traversed from the root node, until both nodes are found. Every time a node is visited, it is added to a dictionary (called parent). Once both nodes are found in the binary tree, the ancestors of node1 are obtained using the dictionary and added to a set (called ancestors). This step is followed in the same manner for node2. If the ancestor of node2 is present in the ancestors set for node1, it is the first common ancestor between them.

Below is the iterative python solution implemented using stack and dictionary with the following points:

• A node can be a descendant of itself
• All nodes in the binary tree are unique
• node1 and node2 will exist in the binary tree

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data  = data
        self.left  = left
        self.right = right

def lowest_common_ancestor(root, node1, node2):
    parent = {root: None}
    stack = [root]
    
    while node1 not in parent or node2 not in parent:
        node = stack[-1]
        stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)
    
    ancestors = set()
    while node1:
        ancestors.add(node1)
        node1 = parent[node1]
    while node2 not in ancestors:
        node2 = parent[node2]
    
    return node2.data

def main():
    '''
    Construct the below binary tree:

            30
           /  \
          /    \
         /      \
        11      29
       /  \    /  \
      8   12  25  14

    '''
    root = Node(30)
    root.left  = Node(11)
    root.right = Node(29)
    root.left.left  = Node(8)
    root.left.right = Node(12)
    root.right.left  = Node(25)
    root.right.right = Node(14)

    print(lowest_common_ancestor(root, root.left.left, root.left.right))       # 11
    print(lowest_common_ancestor(root, root.left.left, root.left))             # 11
    print(lowest_common_ancestor(root, root.left.left, root.right.right))      # 30


if __name__ == '__main__':
    main()

The complexity of this approach is: O(n)

Solution 1: Recursive - Faster

• The idea is to traverse the tree starting from root. If any of the given keys p and q matches with root, then root is LCA, assuming that both keys are present. If root doesn’t match with any of the keys, we recurse for left and right subtree.
• The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.

• Time Complexity: O(n)
• Space Complexity: O(h) - for recursive call stack

class Solution 
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if(root == null || root == p  || root == q)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null)
            return right;
        else if(right == null)
            return left;
        else
            return root;    // If(left != null && right != null)
    }
}

Solution 2: Iterative - Using parent pointers - Slower

• Create an empty hash table.
• Insert p and all of its ancestors in hash table.
• Check if q or any of its ancestors exist in hash table, if yes then return the first existing ancestor.

• Time Complexity: O(n) - In the worst case we might be visiting all the nodes of binary tree.
• Space Complexity: O(n) - Space utilized the parent pointer Hash-table, ancestor_set and queue, would be O(n) each.

class Solution
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
        HashSet<TreeNode> ancestors_set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();

        parent_map.put(root, null);
        queue.add(root);

        while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
        {
            TreeNode node = queue.poll();

            if(node.left != null)
            {
                parent_map.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null)
            {
                parent_map.put(node.right, node);
                queue.add(node.right);
            }
        }

        while(p != null)
        {
            ancestors_set.add(p);
            p = parent_map.get(p);
        }

        while(!ancestors_set.contains(q))
            q = parent_map.get(q);

        return q;
    }
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

The below recursive algorithm will run in O(log N) for a balanced binary tree. If either of the nodes passed into the getLCA() function are the same as the root then the root will be the LCA and there will be no need to perform any recussrion.

Test cases. [1] Both nodes n1 & n2 are in the tree and reside on either side of their parent node. [2] Either node n1 or n2 is the root, the LCA is the root. [3] Only n1 or n2 is in the tree, LCA will be either the root node of the left subtree of the tree root, or the LCA will be the root node of the right subtree of the tree root.

[4] Neither n1 or n2 is in the tree, there is no LCA. [5] Both n1 and n2 are in a straight line next to each other, LCA will be either of n1 or n2 which ever is closes to the root of the tree.

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

Starting from root node and moving downwards if you find any node that has either p or q as its direct child then it is the LCA. (edit - this should be if p or q is the node's value, return it. Otherwise it will fail when one of p or q is a direct child of the other.)

Else if you find a node with p in its right(or left) subtree and q in its left(or right) subtree then it is the LCA.

The fixed code looks like:

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

The below code fails when either is the direct child of other.

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Code In Action

I have made an attempt with illustrative pictures and working code in Java,

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

Some of the solutions here assumes that there is reference to the root node, some assumes that tree is a BST. Sharing my solution using hashmap, without reference to root node and tree can be BST or non-BST:

    var leftParent : Node? = left
    var rightParent : Node? = right
    var map = [data : Node?]()

    while leftParent != nil {
        map[(leftParent?.data)!] = leftParent
        leftParent = leftParent?.parent
    }

    while rightParent != nil {
        if let common = map[(rightParent?.data)!] {
            return common
        }
        rightParent = rightParent?.parent
    }

If someone interested in pseudo code(for university home works) here is one.

GETLCA(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF

public class LeastCommonAncestor {

    private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        TreeNode right;
        int item;

        TreeNode (TreeNode left, TreeNode right, int item) {
            this.left = left;
            this.right = right;
            this.item = item;
        }
    }

    public void createBinaryTree (Integer[] arr) {
        if (arr == null)  {
            throw new NullPointerException("The input array is null.");
        }

        root = new TreeNode(null, null, arr[0]);

        final Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        final int half = arr.length / 2;

        for (int i = 0; i < half; i++) {
            if (arr[i] != null) {
                final TreeNode current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (arr[left] != null) {
                    current.left = new TreeNode(null, null, arr[left]);
                    queue.add(current.left);
                }
                if (right < arr.length && arr[right] != null) {
                    current.right = new TreeNode(null, null, arr[right]);
                    queue.add(current.right);
                }
            }
        }
    }

    private static class LCAData {
        TreeNode lca;
        int count;

        public LCAData(TreeNode parent, int count) {
            this.lca = parent;
            this.count = count;
        }
    }


    public int leastCommonAncestor(int n1, int n2) {
        if (root == null) {
            throw new NoSuchElementException("The tree is empty.");
        }

        LCAData lcaData = new LCAData(null, 0);
       // foundMatch (root, lcaData, n1,  n2);

        /**
         * QQ: boolean was returned but never used by caller.
         */
        foundMatchAndDuplicate (root, lcaData, n1,  n2, new HashSet<Integer>());

        if (lcaData.lca != null) {
            return lcaData.lca.item;
        } else {
            /**
             * QQ: Illegal thrown after processing function.
             */
            throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
        }
    }

//    /**
//     * Duplicate n1, n1         Duplicate in Tree
//     *      x                           x               => succeeds
//     *      x                           1               => fails.
//     *      1                           x               => succeeds by throwing exception
//     *      1                           1               => succeeds
//     */
//    private boolean foundMatch (TreeNode node, LCAData lcaData, int n1, int n2) {
//        if (node == null) {
//            return false;
//        }
//
//        if (lcaData.count == 2) {
//            return false;
//        }
//
//        if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
//            lcaData.count++;
//            return true;
//        }
//
//        boolean foundInCurrent = false;
//        if (node.item == n1 || node.item == n2) {
//            lcaData.count++;
//            foundInCurrent = true;
//        }
//
//        boolean foundInLeft = foundMatch(node.left, lcaData, n1, n2);
//        boolean foundInRight = foundMatch(node.right, lcaData, n1, n2);
//
//        if ((foundInLeft && foundInRight) || (foundInCurrent && foundInRight) || (foundInCurrent && foundInLeft)) {
//            lcaData.lca = node;
//            return true; 
//        }
//        return foundInCurrent || (foundInLeft || foundInRight);
//    }


    private boolean foundMatchAndDuplicate (TreeNode node, LCAData lcaData, int n1, int n2, Set<Integer> set) {
        if (node == null) {
            return false;
        }

        // when both were found
        if (lcaData.count == 2) {
            return false;
        }

        // when only one of them is found
        if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
            if (!set.contains(node.item)) {
                lcaData.count++;
                return true;
            }
        }

        boolean foundInCurrent = false;  
        // when nothing was found (count == 0), or a duplicate was found (count == 1)
        if (node.item == n1 || node.item == n2) {
            if (!set.contains(node.item)) {
                set.add(node.item);
                lcaData.count++;
            }
            foundInCurrent = true;
        }

        boolean foundInLeft = foundMatchAndDuplicate(node.left, lcaData, n1, n2, set);
        boolean foundInRight = foundMatchAndDuplicate(node.right, lcaData, n1, n2, set);

        if (((foundInLeft && foundInRight) || 
                (foundInCurrent && foundInRight) || 
                    (foundInCurrent && foundInLeft)) &&
                        lcaData.lca == null) {
            lcaData.lca = node;
            return true; 
        }
        return foundInCurrent || (foundInLeft || foundInRight);
    }




    public static void main(String args[]) {
        /**
         * Binary tree with unique values.
         */
        Integer[] arr1 = {1, 2, 3, 4, null, 6, 7, 8, null, null, null, null, 9};
        LeastCommonAncestor commonAncestor = new LeastCommonAncestor();
        commonAncestor.createBinaryTree(arr1);

        int ancestor = commonAncestor.leastCommonAncestor(2, 4);
        System.out.println("Expected 2, actual " + ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 7);
        System.out.println("Expected 1, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 6);
        System.out.println("Expected 1, actual " + ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 1);
        System.out.println("Expected 1, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(3, 8);
        System.out.println("Expected 1, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(7, 9);
        System.out.println("Expected 3, actual " +ancestor);

        // duplicate request 
        try {
            ancestor = commonAncestor.leastCommonAncestor(7, 7);
        } catch (Exception e) {
            System.out.println("expected exception");
        }

        /**
         * Binary tree with duplicate values.
         */
        Integer[] arr2 = {1, 2, 8, 4, null, 6, 7, 8, null, null, null, null, 9};
        commonAncestor = new LeastCommonAncestor();
        commonAncestor.createBinaryTree(arr2);

        // duplicate requested
        ancestor = commonAncestor.leastCommonAncestor(8, 8);
        System.out.println("Expected 1, actual " + ancestor);

        ancestor = commonAncestor.leastCommonAncestor(4, 8);
        System.out.println("Expected 4, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(7, 8);
        System.out.println("Expected 8, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 6);
        System.out.println("Expected 1, actual " + ancestor);

         ancestor = commonAncestor.leastCommonAncestor(8, 9);  
        System.out.println("Expected 8, actual " +ancestor); // failed.
    }
}

This can be found at:- http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left == null ? right : right == null ? left : root;
    }

To find out common ancestor of two node :-

• Find the given node Node1 in the tree using binary search and save all nodes visited in this process in an array say A1. Time - O(logn), Space - O(logn)
• Find the given Node2 in the tree using binary search and save all nodes visited in this process in an array say A2. Time - O(logn), Space - O(logn)
• If A1 list or A2 list is empty then one the node does not exist so there is no common ancestor.
• If A1 list and A2 list are non-empty then look into the list until you find non-matching node. As soon as you find such a node then node prior to that is common ancestor.

This would work for binary search tree.

In scala, you can:

  abstract class Tree
  case class Node(a:Int, left:Tree, right:Tree) extends Tree
  case class Leaf(a:Int) extends Tree

  def lca(tree:Tree, a:Int, b:Int):Tree = {
    tree match {
      case Node(ab,l,r) => {
        if(ab==a || ab ==b) tree else {
          val temp = lca(l,a,b);
          val temp2 = lca(r,a,b);
          if(temp!=null && temp2 !=null)
            tree
          else if (temp==null && temp2==null)
            null
          else if (temp==null) r else l
        }

      }
      case Leaf(ab) => if(ab==a || ab ==b) tree else null
    }
  }

The easiest way to find the Lowest Common Ancestor is using the following algorithm:

Examine root node

if value1 and value2 are strictly less that the value at the root node 
    Examine left subtree
else if value1 and value2 are strictly greater that the value at the root node 
    Examine right subtree
else
    return root

public int LCA(TreeNode root, int value 1, int value 2) {
    while (root != null) {
       if (value1 < root.data && value2 < root.data)
           return LCA(root.left, value1, value2);
       else if (value2 > root.data && value2 2 root.data)
           return LCA(root.right, value1, value2);
       else
           return root
    }

    return null;
} 

Consider this tree

If we do postorder and preorder traversal and find the first occuring common predecessor and successor, we get the common ancestor.

postorder => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 preorder => 7,3,1,0,2,6,4,5,12,9,8,11,10,13,15,14

• eg :1

Least common ancestor of 8,11

in postorder we have = >9,14,15,13,12,7 after 8 & 11 in preorder we have =>7,3,1,0,2,6,4,5,12,9 before 8 & 11

9 is the first common number that occurs after 8& 11 in postorder and before 8 & 11 in preorder, hence 9 is the answer

• eg :2

Least common ancestor of 5,10

11,9,14,15,13,12,7 in postorder 7,3,1,0,2,6,4 in preorder

7 is the first number that occurs after 5,10 in postorder and before 5,10 in preorder, hence 7 is the answer

There can be one more approach. However it is not as efficient as the one already suggested in answers.

• Create a path vector for the node n1.

• Create a second path vector for the node n2.

• Path vector implying the set nodes from that one would traverse to reach the node in question.

• Compare both path vectors. The index where they mismatch, return the node at that index - 1. This would give the LCA.

Cons for this approach:

Need to traverse the tree twice for calculating the path vectors. Need addtional O(h) space to store path vectors.

However this is easy to implement and understand as well.

Code for calculating the path vector:

private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) {

        if (treeNode == null) {
            return false;
        }

        pathVector [index++] = treeNode.getKey ();

        if (treeNode.getKey () == key) {
            return true;
        }
        if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) || 
            findPathVector (treeNode.getRightChild(), key, pathVector, index)) {

            return true;        
        }

        pathVector [--index] = 0;
        return false;       
    }

The following is the fastest way to solve this . Space complexity O(1) , Time complexity O(n). If

If a node has both left and right value as not null, then that node is your answer(3rd 'if' from top). While iterating if a value is found, as all the values are uniques and must be present, we don't need to search its descendants. so just return the found node that matched. if a node's both left and right branch contents null propagate null upwards. when reached top-level recursion, if one branch returned value, others do not keep propagating that value, when both returned not null return current node. If it reaches root level recursion with one null and another not null, return not null value, as the question, promises the value exists, it must be in the children tree of the found node which we never traversed.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root.val == p.val || root.val == q.val) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right !=null) return root;
        if (left == null && right ==null) return null;
        return (left != null ? left : right);
    }
}

Well, this kind of depends how your Binary Tree is structured. Presumably you have some way of finding the desired leaf node given the root of the tree - simply apply that to both values until the branches you choose diverge.

If you don't have a way to find the desired leaf given the root, then your only solution - both in normal operation and to find the last common node - is a brute-force search of the tree.

You are correct that without a parent node, solution with traversal will give you O(n) time complexity.

Traversal approach Suppose you are finding LCA for node A and B, the most straightforward approach is to first get the path from root to A and then get the path from root to B. Once you have these two paths, you can easily iterate over them and find the last common node, which is the lowest common ancestor of A and B.

Recursive solution Another approach is to use recursion. First, we can get LCA from both left tree and right tree (if exists). If the either of A or B is the root node, then the root is the LCA and we just return the root, which is the end point of the recursion. As we keep divide the tree into sub-trees, eventually, we’ll hit either A and B.

To combine sub-problem solutions, if LCA(left tree) returns a node, we know that both A and B locate in left tree and the returned node is the final result. If both LCA(left) and LCA(right) return non-empty nodes, it means A and B are in left and right tree respectively. In this case, the root node is the lowest common node.

Check Lowest Common Ancestor for detailed analysis and solution.

The code in Php. I've assumed the tree is an Array binary tree. Therefore, you don't even require the tree to calculate the LCA. input: index of two nodes output: index of LCA

    <?php
 global $Ps;

function parents($l,$Ps)
{

    if($l % 2 ==0)
        $p = ($l-2)/2;
    else            
        $p = ($l-1)/2;

    array_push($Ps,$p);     
    if($p !=0)
        parents($p,$Ps);

    return $Ps; 
}
function lca($n,$m)
{
    $LCA = 0;
    $arr1 = array();
    $arr2 = array();
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr1 = parents($n,$arr1);
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr2 = parents($m,$arr2);

    if(count($arr1) > count($arr2))
        $limit = count($arr2);
    else
        $limit = count($arr1);

    for($i =0;$i<$limit;$i++)
    {
        if($arr1[$i] == $arr2[$i])
        {
            $LCA = $arr1[$i];
            break;
        }
    }
    return $LCA;//this is the index of the element in the tree

}

var_dump(lca(5,6));
?>

Do tell me if there are any shortcomings.

Here is what I think,

1. Find the route for the fist node , store it on to arr1.
2. Start finding the route for the 2 node , while doing so check every value from root to arr1.
3. time when value differs , exit. Old matched value is the LCA.

Complexity : step 1 : O(n) , step 2 =~ O(n) , total =~ O(n).

//If both the values are less than the current node then traverse the left subtree //Or If both the values are greater than the current node then traverse the right subtree //Or LCA is the current node

public BSTNode findLowestCommonAncestor(BSTNode currentRoot, int a, int b){
    BSTNode commonAncestor = null;
    if (currentRoot == null) {
        System.out.println("The Tree does not exist");
        return null;
    }

    int currentNodeValue = currentRoot.getValue();
    //If both the values are less than the current node then traverse the left subtree
    //Or If both the values are greater than the current node then traverse the right subtree
    //Or LCA is the current node
    if (a < currentNodeValue && b < currentNodeValue) {
        commonAncestor = findLowestCommonAncestor(currentRoot.getLeft(), a, b);
    } else if (a > currentNodeValue && b > currentNodeValue) {
        commonAncestor = findLowestCommonAncestor(currentRoot.getRight(), a, b);
    } else {
        commonAncestor = currentRoot;
    }

    return commonAncestor;
}

Here are two approaches in c# (.net) (both discussed above) for reference:

1. Recursive version of finding LCA in binary tree (O(N) - as at most each node is visited) (main points of the solution is LCA is (a) only node in binary tree where both elements reside either side of the subtrees (left and right) is LCA. (b) And also it doesn't matter which node is present either side - initially i tried to keep that info, and obviously the recursive function become so confusing. once i realized it, it became very elegant.

2. Searching both nodes (O(N)), and keeping track of paths (uses extra space - so, #1 is probably superior even thought the space is probably negligible if the binary tree is well balanced as then extra memory consumption will be just in O(log(N)).

   so that the paths are compared (essentailly similar to accepted answer - but the paths is calculated by assuming pointer node is not present in the binary tree node)

3. Just for the completion (not related to question), LCA in BST (O(log(N))

4. Tests

Recursive:

private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, 
            int e1, int e2)
        {
            Debug.Assert(e1 != e2);
            
            if(treeNode == null)
            {
                return null;
            }
            if((treeNode.Element == e1)
                || (treeNode.Element == e2))
            {
                //we don't care which element is present (e1 or e2), we just need to check 
                //if one of them is there
                return treeNode;
            }
            var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
            var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
            if(nLeft != null && nRight != null)
            {
                //note that this condition will be true only at least common ancestor
                return treeNode;
            }
            else if(nLeft != null)
            {
                return nLeft;
            }
            else if(nRight != null)
            {
                return nRight;
            }
            return null;
        }

where above private recursive version is invoked by following public method:

public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
        {
            var n = this.FindNode(this._root, e1);
            if(null == n)
            {
                throw new Exception("Element not found: " + e1);
            }
            if (e1 == e2)
            {   
                return n;
            }
            n = this.FindNode(this._root, e2);
            if (null == n)
            {
                throw new Exception("Element not found: " + e2);
            }
            var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
            if (null == node)
            {
                throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
            }
            return node;
        }

Solution by keeping track of paths of both nodes:

public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
        {
            var path1 = new List<BinaryTreeNode>();
            var node1 = this.FindNodeAndPath(this._root, e1, path1);
            if(node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e1));
            }
            if(e1 == e2)
            {
                return node1;
            }
            List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
            var node2 = this.FindNodeAndPath(this._root, e2, path2);
            if (node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e2));
            }
            BinaryTreeNode lca = null;
            Debug.Assert(path1[0] == this._root);
            Debug.Assert(path2[0] == this._root);
            int i = 0;
            while((i < path1.Count)
                && (i < path2.Count)
                && (path2[i] == path1[i]))
            {
                lca = path1[i];
                i++;
            }
            Debug.Assert(null != lca);
            return lca;
        }

where FindNodeAndPath is defined as

private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
        {
            if(node == null)
            {
                return null;
            }
            if(node.Element == e)
            {
                path.Add(node);
                return node;
            }
            var n = this.FindNodeAndPath(node.Left, e, path);
            if(n == null)
            {
                n = this.FindNodeAndPath(node.Right, e, path);
            }
            if(n != null)
            {
                path.Insert(0, node);
                return n;
            }
            return null;
        }

BST (LCA) - not related (just for completion for reference)

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
        {
            //ensure both elements are there in the bst
            var n1 = this.BstFind(e1, throwIfNotFound: true);
            if(e1 == e2)
            {
                return n1;
            }
            this.BstFind(e2, throwIfNotFound: true);
            BinaryTreeNode leastCommonAcncestor = this._root;
            var iterativeNode = this._root;
            while(iterativeNode != null)
            {
                if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
                {
                    iterativeNode = iterativeNode.Left;
                }
                else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                {
                    iterativeNode = iterativeNode.Right;
                }
                else
                {
                    //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                    return iterativeNode;
                }
            }
            //control will never come here
            return leastCommonAcncestor;
        }

Unit Tests

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
                var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
                Assert.IsTrue(n1.Element == b[i]);
                Assert.IsTrue(n == n1);
                var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
                Assert.IsTrue(n2.Element == b[i]);
                Assert.IsTrue(n2 == n1);
                Assert.IsTrue(n2 == n);
            }
        }

Tarjan's off-line least common ancestors algorithm is good enough (cf. also Wikipedia). There is more on the problem (the lowest common ancestor problem) on Wikipedia.

Here is the working code in JAVA

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

The answers given so far uses recursion or stores, for instance, a path in memory.

Both of these approaches might fail if you have a very deep tree.

Here is my take on this question. When we check the depth (distance from the root) of both nodes, if they are equal, then we can safely move upward from both nodes towards the common ancestor. If one of the depth is bigger then we should move upward from the deeper node while staying in the other one.

Here is the code:

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

The time complexity of this algorithm is: O(n). The space complexity of this algorithm is: O(1).

Regarding the computation of the depth, we can first remember the definition: If v is root, depth(v) = 0; Otherwise, depth(v) = depth(parent(v)) + 1. We can compute depth as follows:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

Crude way:

• At every node
  • X = find if either of the n1, n2 exist on the left side of the Node
  • Y = find if either of the n1, n2 exist on the right side of the Node
    • if the node itself is n1 || n2, we can call it either found on left or right for the purposes of generalization.
  • If both X and Y is true, then the Node is the CA

The problem with the method above is that we will be doing the "find" multiple times, i.e. there is a possibility of each node getting traversed multiple times. We can overcome this problem if we can record the information so as to not process it again (think dynamic programming).

So rather than doing find every node, we keep a record of as to whats already been found.

Better Way:

• We check to see if for a given node if left_set (meaning either n1 | n2 has been found in the left subtree) or right_set in a depth first fashion. (NOTE: We are giving the root itself the property of being left_set if it is either n1 | n2)
• If both left_set and right_set then the node is a LCA.

Code:

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}

I found a solution

1. Take inorder
2. Take preorder
3. Take postorder

Depending on 3 traversals, you can decide who is the LCA. From LCA find distance of both nodes. Add these two distances, which is the answer.

Just walk down from the whole tree's root as long as both given nodes ,say p and q, for which Ancestor has to be found, are in the same sub-tree (meaning their values are both smaller or both larger than root's).

This walks straight from the root to the Least Common Ancestor , not looking at the rest of the tree, so it's pretty much as fast as it gets. A few ways to do it.

Iterative, O(1) space

Python

def lowestCommonAncestor(self, root, p, q):
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = (root.left, root.right)[p.val > root.val]
    return root

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

in case of overflow, I'd do (root.val - (long)p.val) * (root.val - (long)q.val)

Recursive

Python

def lowestCommonAncestor(self, root, p, q):
    next = p.val < root.val > q.val and root.left or \
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Although this has been answered already, this is my approach to this problem using C programming language. Although the code shows a binary search tree (as far as insert() is concerned), but the algorithm works for a binary tree as well. The idea is to go over all nodes that lie from node A to node B in inorder traversal, lookup the indices for these in the post order traversal. The node with maximum index in post order traversal is the lowest common ancestor.

This is a working C code to implement a function to find the lowest common ancestor in a binary tree. I am providing all the utility functions etc. as well, but jump to CommonAncestor() for quick understanding.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

static inline int min (int a, int b)
{
    return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
    return ((a > b) ? a : b);
}

typedef struct node_ {
    int value;
    struct node_ * left;
    struct node_ * right;
} node;

#define MAX 12

int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};

createNode(int value) 
{
    node * temp_node = (node *)malloc(sizeof(node));
    temp_node->left = temp_node->right = NULL;
    temp_node->value = value;
    return temp_node;
}

node *
insert(node * root, int value)
{
    if (!root) {
        return createNode(value);
    }

    if (root->value > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}


/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
    static int i = 0;

    if (!root) return;

    inorder(root->left, IN);
    IN[i] = root->value;
    i++;
    inorder(root->right, IN);
}

/* Builds post traversal path in the POST array */

void
postorder (node * root, int * POST)
{
    static int i = 0;

    if (!root) return;

    postorder(root->left, POST);
    postorder(root->right, POST);
    POST[i] = root->value;
    i++;
}


int
findIndex(int * A, int value)
{
    int i = 0;
    for(i = 0; i< MAX; i++) {
        if(A[i] == value) return i;
    }
}
int
CommonAncestor(int val1, int val2)
{
    int in_val1, in_val2;
    int post_val1, post_val2;
    int j=0, i = 0; int max_index = -1;

    in_val1 = findIndex(IN_ORDER, val1);
    in_val2 = findIndex(IN_ORDER, val2);
    post_val1 = findIndex(POST_ORDER, val1);
    post_val2 = findIndex(POST_ORDER, val2);

    for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
        for(j = 0; j < MAX; j++) {
            if (IN_ORDER[i] == POST_ORDER[j]) {
                if (j > max_index) {
                    max_index = j;
                }
            }
        }
    }
    printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]);
    return max_index;
}
int main()
{
    node * root = NULL; 

    /* Build a tree with following values */
    //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
    root = insert(root, 40);
    insert(root, 20);
    insert(root, 10);
    insert(root, 30);
    insert(root, 5);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 1);
    insert(root, 80);
    insert(root, 60);
    insert(root, 100);

    /* Get IN_ORDER traversal in the array */
    inorder(root, IN_ORDER);

    /* Get post order traversal in the array */
    postorder(root, POST_ORDER);

    CommonAncestor(1, 100);


}

If it is full binary tree with children of node x as 2*x and 2*x+1 than there is a faster way to do it

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  
}

How does it work

1. get bits needed to represent x & y which using binary search is O(log(32))
2. the common prefix of binary notation of x & y is the common ancestor
3. whichever is represented by larger no of bits is brought to same bit by k >> diff
4. k = x^y erazes common prefix of x & y
5. find bits representing the remaining suffix
6. shift x or y by suffix bits to get common prefix which is the common ancestor.

This works because basically divide the larger number by two recursively until both numbers are equal. That number is the common ancestor. Dividing is effectively the right shift opearation. So we need to find common prefix of two numbers to find the nearest ancestor

Code for A Breadth First Search to make sure both nodes are in the tree. Only then move forward with the LCA search. Please comment if you have any suggestions to improve. I think we can probably mark them visited and restart the search at a certain point where we left off to improve for the second node (if it isn't found VISITED)

public class searchTree {
    static boolean v1=false,v2=false;
    public static boolean bfs(Treenode root, int value){
         if(root==null){
           return false;
     }
    Queue<Treenode> q1 = new LinkedList<Treenode>();

    q1.add(root);
    while(!q1.isEmpty())
    {
        Treenode temp = q1.peek();

        if(temp!=null) {
            q1.remove();
            if (temp.value == value) return true;
            if (temp.left != null) q1.add(temp.left);
            if (temp.right != null) q1.add(temp.right);
        }
    }
    return false;

}
public static Treenode lcaHelper(Treenode head, int x,int y){

    if(head==null){
        return null;
    }

    if(head.value == x || head.value ==y){
        if (head.value == y){
            v2 = true;
            return head;
        }
        else {
            v1 = true;
            return head;
        }
    }

    Treenode left = lcaHelper(head.left, x, y);
    Treenode right = lcaHelper(head.right,x,y);

    if(left!=null && right!=null){
        return head;
    }
    return (left!=null) ? left:right;
}

public static int lca(Treenode head, int h1, int h2) {
    v1 = bfs(head,h1);
    v2 = bfs(head,h2);
    if(v1 && v2){
        Treenode lca = lcaHelper(head,h1,h2);
        return lca.value;
    }
    return -1;
}
}

Try like this

node * lca(node * root, int v1,int v2)
{

if(!root) {
            return NULL;
    }
    if(root->data == v1 || root->data == v2) {
        return root;}
    else
    {
        if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
        {
            return root;
        }

        if(v1 < root->data && v2 < root->data)
        {
            root = lca(root->left, v1, v2);
        }

        if(v1 > root->data && v2 > root->data)
        {
            root = lca(root->right, v1, v2);
        }
    }
return root;
}