Thursday, September 17, 2015

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!

Tuesday, September 1, 2015

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!

-Jim

Thursday, August 27, 2015

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

Wednesday, August 26, 2015

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?

-Jim

Wednesday, August 5, 2015

*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:

20

/ \

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 **reference**. **You 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.