James Michael Hare

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

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

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:

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

Print | posted on Wednesday, August 5, 2015 10:59 AM |

Powered by: