Lowest Common Ancestor of a Binary Tree

Question

This is a popular interview question and the only article I can find on the topic is one from TopCoder. Unfortunately for me, it looks overly complicated from an interview answer's perspective.

Isn't there a simpler way of doing this other than plotting the path to both nodes and deducing the ancestor? (This is a popular answer, but there's a variation of the interview question asking for a constant space answer).

Answer 1

A simplistic (but much less involved version) could simply be (.NET guy here Java a bit rusty, so please excuse the syntax, but I think you won't have to adjust too much). This is what I threw together.

class Program
{
    static void Main(string[] args)
    {
        Node node1 = new Node { Number = 1 };
        Node node2 = new Node { Number = 2, Parent = node1 };
        Node node3 = new Node { Number = 3, Parent = node1 };
        Node node4 = new Node { Number = 4, Parent = node1 };
        Node node5 = new Node { Number = 5, Parent = node3 };
        Node node6 = new Node { Number = 6, Parent = node3 };
        Node node7 = new Node { Number = 7, Parent = node3 };
        Node node8 = new Node { Number = 8, Parent = node6 };
        Node node9 = new Node { Number = 9, Parent = node6 };
        Node node10 = new Node { Number = 10, Parent = node7 };
        Node node11 = new Node { Number = 11, Parent = node7 };
        Node node12 = new Node { Number = 12, Parent = node10 };
        Node node13 = new Node { Number = 13, Parent = node10 };

        Node commonAncestor = FindLowestCommonAncestor(node9, node12);

        Console.WriteLine(commonAncestor.Number);
        Console.ReadLine();
    }

    public class Node
    {
        public int Number { get; set; }
        public Node Parent { get; set; }
        public int CalculateNodeHeight()
        {
            return CalculateNodeHeight(this);
        }

        private int CalculateNodeHeight(Node node)
        {
            if (node.Parent == null)
            {
                return 1;
            }

            return CalculateNodeHeight(node.Parent) + 1;
        }
    }

    public static Node FindLowestCommonAncestor(Node node1, Node node2)
    {
        int nodeLevel1 = node1.CalculateNodeHeight();
        int nodeLevel2 = node2.CalculateNodeHeight();

        while (nodeLevel1 > 0 && nodeLevel2 > 0)
        {
            if (nodeLevel1 > nodeLevel2)
            {
                node1 = node1.Parent;
                nodeLevel1--;
            }
            else if (nodeLevel2 > nodeLevel1)
            {
                node2 = node2.Parent;
                nodeLevel2--;
            }
            else
            {
                if (node1 == node2)
                {
                    return node1;
                }

                node1 = node1.Parent;
                node2 = node2.Parent;
                nodeLevel1--;
                nodeLevel2--;
            }
        }

        return null;
    }
}

Answer 2

Constant space answer: (although not necessarily efficient).

Have a function findItemInPath(int index, int searchId, Node root)

then iterate from 0 .. depth of tree, finding the 0-th item, 1-th item etc. in both search paths.

When you find i such that the function returns the same result for both, but not for i+1, then the i-th item in the path is the lowest common ancestor.