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
2: {
3: T Data { get; set; }
4: Node Left { get; set; }
5: Node Right { get; set; }
6: }
And a reference to the root of the tree:
1: Node 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.