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

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

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.

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

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

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);
    }
}