James Michael Hare

Solution to Little Puzzlers - Lowest Common Ancestor

This is the way I went about the "Lowest Common Ancestor" problem. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

The Solution

The first tendency in this problem is to want to walk back up the tree.  This is obviously problematic because we do not have a parent node link at each node.  But, it turns out, there’s a better way anyway.

The first thing we want to do is examine the two values we are sent to find.  If the values are the same, they are obviously their own common ancestor – as long as the node actually exists in the tree.

If the nodes aren’t the same, we will “order” them by simply finding which node is less and which is greater.  Why do we care?  Because, it will simplify our search to be O(log n) by allowing us to drive down the tree in the BST fashion.

What we can do at each node, is take advantage of the ordering to tell us where to go.  If the current node’s value is < the smaller value, we know both nodes are on the right (if they exist in the tree).  Similarly, if the current node’s value is > the larger value, we know both nodes are on the left (if they exist in the tree). 

If neither of these conditions are true, one of two things are true: either a) one of the nodes equals the current node or b) the smaller is on the left and the larger is on the right.  Either way, we have a candidate for the LCA as long as both nodes are in the tree.  So, once we know this is the point that the LCA would be, we simply find the smaller and larger in this subtree.

   1: public class Trees 

   2: { 

   3:     // This is the public kick-off method, orders the first/second

   4:     public Node<int> FindLowestCommonAncestor(int first, int second, Node<int> root) 

   5:     { 

   6:         // if first and second happen to be same, it's simply a find

   7:         if (first == second) 

   8:         { 

   9:             return Find(first, root); 

  10:         }

  11:         

  12:         // otherwise, order the first and second by value

  13:         return first < second 

  14:             ? FindLowestCommonAncestorTraversal(first, second, root) 

  15:             : FindLowestCommonAncestorTraversal(second, first, root); 

  16:     }

  17:  

  18:     // a helper method that simply finds a node in the BST

  19:     public Node<int> Find(int value, Node<int> current) 

  20:     { 

  21:         if (current != null) 

  22:         { 

  23:             if (current.Value == value) 

  24:             { 

  25:                 return current; 

  26:             }

  27:  

  28:             return value < current.Value 

  29:                 ? Find(value, current.Left) 

  30:                 : Find(value, current.Right); 

  31:         }

  32:  

  33:         return null; 

  34:     }

  35:     

  36:     // the actual traversal

  37:     private Node<int> FindLowestCommonAncestorTraversal(int smaller, int larger, Node<int> current) 

  38:     { 

  39:         if (current != null) 

  40:         { 

  41:             // if larger < value then smaller is also by definition, both left

  42:             if (larger < current.Value) 

  43:             { 

  44:                 return FindLowestCommonAncestorTraversal(smaller, larger, current.Left); 

  45:             } 

  46:  

  47:             // if smaller is > value, then larger is also by definition, both right

  48:             if (smaller > current.Value) 

  49:             { 

  50:                 return FindLowestCommonAncestorTraversal(smaller, larger, current.Right); 

  51:             }

  52:  

  53:             // otherwise, we found divergent point, make sure nodes actually exist

  54:             if (Find(smaller, current) != null && Find(larger, current) != null) 

  55:             { 

  56:                 return current; 

  57:             } 

  58:         }

  59:  

  60:         return null; 

  61:     } 

  62: }

This algorithm ends up being O(log n) – assuming a well balanced BST implementation, which is fairly optimal.  At most, we’d find the LCA at the root, which would mean we’d do two finds, both of which are O(log n).

Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.

• Share This Post:
• 
• 
• 
•   Short Url: http://wblo.gs/hJo

Print | posted on Thursday, August 27, 2015 12:52 AM | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology ]