title: Fastest non-recursive implementation of LCA?
body: <p>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:</p>
  
  <ol>
  <li>Use a dictionary/hashtable to store the tree.  Each key-value pair represents a node and its parent.</li>
  <li>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).</li>
  <li>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).</li>
  </ol>
  
  <p>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)).</p>
  
  <p>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:</p>
  
  <pre><code>int LowestCommonAncestor(int value1, int value2, Dictionary&lt;int, int&gt; tree)
  {
      var value1Visited = new HashSet&lt;int&gt;();
      var value2Visited = new HashSet&lt;int&gt;();
      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;
          }
      }
  }
  </code></pre>