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

Article Categories

Archives

Post Categories

Image Galleries

.NET

CSharp

Little Wonders

Little Wonders

vNext

Little Puzzlers–Is Tree a Binary Search Tree?

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:

Given a standard definition of a binary tree node, i.e.:

   1: public class Node<T>
   2: {
   3:     ​T Data { get; set; }
   4:     Node<T> Left { get; set; }
   5:     Node<T> Right { get; set; }
   6: }

And a reference to the root of the tree:

   1: Node<T> root = ....;

Write a method that will determine if the tree has the ordered property.  A binary tree has the ordered property such that for any node x, the left sub-tree of x is < x and the right sub-tree of x is > x for all nodes. 

Examples:

That is, the following tree has the ordered property:

           5

        /    \        

      3        7      

    /   \     /       

   2     4   6     

But this tree does not:               

           5

        /    \        

      3        8      

    /   \     /       

   2     6   7     

Because even though 6 is on the right of 3 and is > 3, it is on the left sub-tree of 5 so it must be < 5.

Spoiler Alert

Fair Warning: discussion of the problem and potential solutions may be discussed in the comments below. 

Print | posted on Monday, March 23, 2015 9:05 AM |

Powered by: