James Michael Hare

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

My Links

News

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

Archives

.NET

CSharp

Little Wonders

Little Wonders

vNext

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.

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

Feedback

Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

I stole the tree building framework from Keith Nicholas's since he did such a good job on that. do my coursework. I just changed the method dealing with the Lowest Common Ancestor algorithm.
8/1/2016 4:40 AM | WilliamStewart
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

<a href=”http://www.writerhelp.co.uk/writers-voice-how-to-get-an-australian-student-visa">essay writing services
The most recent trending shows a high percentage of students opting for studies abroad, and among these abroad destinations, Australia and the top most one. This because you can not only study at Australia but also you are allowed to work to earn your living. The time period for this visa is equal to the time required to complete the course or degree. Before applying for this Visa, you should know that your age requirements are required to be above 16. Moreover, the courses most rapidly available for the foreigners include the language courses, in which you will find General English, IELTS Preparation and so on. Other than this, buy coursework online
12/12/2016 10:59 PM | sarevirginia
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: Nursing Dissertation Help the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor.
12/20/2016 10:15 PM | Aaron Abbey
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

A coursework writing service can be of immense help for such organisation to hire an expert to undertake a research. According to the concept of compliance with the national as well as international laws, organizations are increasingly facing the troubles with dealing the ethical issues because they do not identify the compliance of laws as essential part of their ethical code of conduct.
1/10/2017 9:47 PM | Julia Charles
Gravatar

# Write My Research Paper

The latest inclining demonstrates a high rate of understudies selecting concentrates abroad, and among these abroad goals, Australia and the top generally one. This since you can learn at Australia as well as you are permitted to work to win your living. The day and age for this visa is equivalent to the time required to finish the course or degree.
2/14/2017 2:43 AM | John Marshal
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

According to the concept of compliance with the national as well as international laws, companies are progressively facing the troubles with dealing the ethical issues because they do not identify the compliance of laws as essential part of their ethical code of executing. Coursework Writing Services
3/1/2017 7:11 PM | Johny Thomas
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

I went through your code and I am very impressed with the way how you have done. I don’t think there is a better way to do this. I had tried creating a program for this too but I couldn’t do it. http://buywholesaletablets.com
3/17/2017 4:17 AM | Gemma Carter
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

According to the concept of compliance with the national as well as international laws, companies are progressively facing the troubles with dealing the ethical issues because they do not identify the compliance of laws as essential part of their ethical code of executing. Coursework Writing Services
3/28/2017 11:50 PM | Alen
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

I went through your code and I am very impressed with the way how you have done. I don’t think there is a better way to do this. I had tried creating a program for this too but I couldn’t do it. academic dissertation service
4/2/2017 9:26 PM | Daisy Faith
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

The little puzzler can't be solve easily it requires many things which are going to be the best among all and for that instance it can be solve in a decent Essay Writing Online way and the puzzler has been common ancestor which is not solved easily and the revolutionary act is required to solve that thing in a proper way.
4/3/2017 11:33 PM | Eloise Leach
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

I don’t understand why we have to study all this. This puzzle was there since I was in school and I can’t believe that they are using this still with the kids. Why do we need things like this? I hate puzzles. lip mask
4/21/2017 2:12 AM | Melodie Raymond
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

There are multiple ways to solve this problem. You have provided a different solution that can help us in solving the problem. But I didn’t understand the program that you have provided here. It will be good if you make it clear so that all can solve this puzzle. affordable hotels in catalina island
4/22/2017 4:59 AM | Nikita
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by: