Fastest non-recursive implementation of LCA?

Question

Here's the algorithm I came up with for non-recursively finding the lowest common ancestor of two nodes in a binary tree. Here's the basic strategy:

1. Use a dictionary/hashtable to store the tree. Each key-value pair represents a node and its parent.
2. Starting from each of the two nodes, walk up the tree by setting the variable representing each node's value to that of its parent, storing traversed values in a hashset (one for each of the two nodes).
3. The search is complete when any of the following conditions are reached: (a) the value of the two nodes is equal; or (b) when the two paths cross each other (i.e., the hashset of node 1's traversed values contains the current value for node 2, or vice versa); or (c) the node passed in doesn't exist in the tree (in which case the algorithm terminates and returns -1).

My understanding is that the worst-case time and space complexity of my algorithm is O(log(n)), since we never need to make more than 2 * height traversals or store more than 2 * height values in our hashsets (and since the lookup time for the hashsets and the tree dictionary are O(1)).

Following is my code (C#). Please advise if I am correct in my analysis, or if there is a more efficient (non-recursive) way to do this:

int LowestCommonAncestor(int value1, int value2, Dictionary<int, int> tree)
{
    var value1Visited = new HashSet<int>();
    var value2Visited = new HashSet<int>();
    while (true)
    {
        if (value1 == value2) return value1;
        if (value1Visited.Contains(value2)) return value2;
        if (value2Visited.Contains(value1)) return value1;

        int nextValue1;
        int nextValue2;

        if (tree.TryGetValue(value1, out nextValue1))
        {
            //Walk node 1 up the tree:
            value1 = nextValue1;
            value1Visited.Add(value1);
        }
        else
        {
            //Node doesn't exist in tree:
            return -1;
        }

        if (tree.TryGetValue(value2, out nextValue2))
        {
            //Walk node 2 up the tree:
            value2 = nextValue2;
            value2Visited.Add(value2);
        }
        else
        {
            //Node doesn't exist in tree:
            return -1;
        }
    }
}

Answer 1

1. Go up from each node to the root to measure its depth

2. Move up the path from the deeper node until you get to the same depth as the shallower one.

3. Move up the paths from both nodes (i.e., keeping the same depth on both paths) until they meet.

Answer 2

You don't need two hash sets.

1. Go up and collect in a single hash set the ancestors of one node
2. Go up from the second node and at each of its ancestors, check if the path collected at step 1 contains the current ancestor of the second. Stop at the first common one.

With D being the max depth of the tree, the complexity is O(D) worst-case complexity.

The worst case complexity in N - number of nodes - when the tree is degenerated in a list, one of the node being the head of this list and the other is the tail.

If the tree is balanced, D=log(N) - with log's base being the number of descendents of a node (binary - log2, ternary - log3, etc).

Answer 3

Here, then, is my revised algorithm:

int LCA(int value1, int value2, Dictionary<int, int> tree)
{
    if (!tree.ContainsKey(value1) || !(tree.ContainsKey(value2))) return -1;

    int depth1 = 0;
    int depth2 = 0;
    int tmpVal1 = value1;
    int tmpVal2 = value2;

    while (tmpVal1 != -1)
    {
        tmpVal1 = tree[tmpVal1];
        depth1++;
    }

    while (tmpVal2 != -1)
    {
        tmpVal2 = tree[tmpVal2];
        depth2++;
    }

    if (depth1 > depth2)
    {
        while (depth1 > depth2)
        {
            value1 = tree[value1];
            depth1--;
        }
    }

    else if (depth2 > depth1)
    {
        while (depth2 > depth1)
        {
            value2 = tree[value2];
            depth2--;
        }
    }
    while (value1 != value2)
    {
        value1 = tree[value1];
        value2 = tree[value2];
    }

    return value1;
}