James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1517 , 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

Article Categories

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
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

I experienced your code and I am exceptionally awed with the way how you have done. I don't think there is a superior approach. I had a go at making a program for this as well yet I couldn't do it. scholarly thesis benefit best academic writing service
5/3/2017 8:23 AM | Davin Parkin
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

A hand written letter can be a highly prized possession, especially in this era of emails and online chatting. But a hand written letter on high quality writing paper can make it even more prized, enhancing the reading experience.
need a paper written now
5/21/2017 7:27 AM | h b
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

Thanks for the step by step instruction. It really helped me to get a better idea of the problem and how to solve it. There are many other ways and in most cases the simplest ways often end up pretty long. oren loni burgerim
6/1/2017 3:48 AM | Taylor Shaw
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

I would say, the way you have explained the '"Lowest Common Ancestor" really helped the readers understand the solution and work out on the same. You had tried to explain it in a slow method and in detail. I am very glad to find your Tech Support Instant page and get those details.
7/21/2017 3:50 AM | steve larsc
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

Hey admin your sharing way is unique. This is fantastic site.I enjoyed reading your articles. This is truly a great read for me. JN0-102 Dumps Questions

7/28/2017 4:52 AM | Rogersmith
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

I remember creating the code for this when i studied in college.This was one task i was assigned by the teachers during my second year of college. I had to spend a whole day on it. Degree Certificate Attestation
8/30/2017 2:11 AM | deb
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

Rest assured that the profound experience— we are backed by— help us overcome all your fears, skepticism and demands. We can provide you the sample of essays we have previously written to help you gauge their quality and originality. We also provide you with an anti-plagiarism report as a testament to the originality, let alone the refund guarantee in order to assure the security of your money. At Hire Researchers UK, we help students get quality essays at rates that are so easy to afford. So, be certain that when you have our UK writers by your side, you are going to inspire your teacher and class, for sure.
9/18/2017 3:34 AM | annabia
Gravatar

# re: Solution to Little Puzzlers - Lowest Common Ancestor

Little puzzler is a very exciting one for the users and they have been coming up with a lot of interesting tasks. The new one to find the lowest common ancestor looks good from the details provided here. I will definitely give it a try soon. Merito sober living home
9/20/2017 3:31 AM | lionel john
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by: