James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 161 , comments - 1348 , trackbacks - 0

My Links


Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud


Post Categories



Little Wonders

Little Wonders


Thursday, September 17, 2015

Life in Motion

Just as an update.  We've recently moved back to the Pacific Northwest and have been mostly busy after work with unpacking and getting the house in order.  More Little Wonders and Little Puzzlers are on the way, though!

Posted On Thursday, September 17, 2015 9:26 AM | Comments (0) |

Tuesday, September 1, 2015

Wonky RSS Feed

Hey folks, many of you have complained about the wonky RSS feed.  Yes, it is still a problem and I'm looking at it.

It appears as if my feed is getting re-published to different sources, which explains why folks are seeing multiple copies of my post, each with a different source URL.

I'm going to check with my blog hosting company to see if there's a reason this is happening on their end.

Thanks so much for your patience!


Posted On Tuesday, September 1, 2015 2:52 PM | Comments (2) |

Thursday, August 27, 2015

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:         }
  12:         // otherwise, order the first and second by value
  13:         return first < second 
  14:             ? FindLowestCommonAncestorTraversal(first, second, root) 
  15:             : FindLowestCommonAncestorTraversal(second, first, root); 
  16:     }
  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:             }
  28:             return value < current.Value 
  29:                 ? Find(value, current.Left) 
  30:                 : Find(value, current.Right); 
  31:         }
  33:         return null; 
  34:     }
  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:             } 
  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:             }
  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:         }
  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).


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.

Posted On Thursday, August 27, 2015 12:52 AM | Comments (0) | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology ]

Wednesday, August 26, 2015

Back in Seattle Again

Hey folks, after 8 months back in the mid-west, we had a family meeting and decided that it would be better for my career and our kids to go back to Seattle.  We're relocated again, though still waiting for all of our computers, furtniture, etc. 

As soon as I can, I will post the solution to the latest puzzler, and send you a new one! 

To those who were noticing duplications in my feed, I believe I fixed this, is anyone still noticing issues?


Posted On Wednesday, August 26, 2015 5:07 PM | Comments (8) | Filed Under [ My Blog ]

Wednesday, August 5, 2015

Little Puzzlers–Lowest Common Ancestor

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

The Problem

A binary search tree is a tree with the ordered property.  That is, for every node in the tree with value x, all nodes in the left subtree are < x and all nodes in the right subtree are > x recursively.

So, given a binary search tree (BST) and two values, determine the lowest common ancestor of the two values.  That is, tracing up from the values, towards the root, find the lowest node (level wise) they have in common.

For example, given the following tree:


                    /          \

                  10            30

                /    \        /     \

               5      15    25       35

The Lowest Common Ancestor (LCA) of 5 and 15 is 10.  Similarly, the lowest common ancestor of 5 and 35 is 20.  Note that the value itself could be it’s own LCA, for example, the LCA of 20 and 35 is 20.

The tree itself is composed of standard nodes that only go down.  That is, they have a Left and Right child reference but not a Parent referenceYou may use the following as your template for a node class:

public class Node<T>
    public T Value { get; private set; }

    public Node<T> Left { get; set; }

    public Node<T> Right { get; set; }

    public Node(T value)
        Value = value;

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

Posted On Wednesday, August 5, 2015 10:59 AM | Comments (8) |

Powered by: