## 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 ]

## Feedback

## # 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.## # 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 servicesThe 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

## # 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.## # 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.## # 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.## # 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## # 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