## Solution: Little Puzzlers–Is tree a Binary Search Tree?

This is the way I would go about the “Is tree a Binary Search Tree” problem if I were asked to perform it at an evaluation. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations.

### The Wrong Path

The temptation here is to naively think of a BST as simply having the restriction that the left child of *x* must be *< x* and the right child of *x* must be *> x.*

The problem is that this is not the accurate definition. The definition of a BST is that the left **subtree **of *x* must be *< x* and the right **subtree **of *x* must be *> x, *which is more complex to check.

5

/ \

3 8

/ \ /

2 6 7

Notice that the tree above satisfies the naïve rule for every child, but not for the whole subtree. Thus, this is not a BST because even though **6** > **3**, it is not < **5 **so it cannot be on the left subtree of 5.

### My Solution: Diminishing Ranges

One way to tackle this is to traverse the tree keeping track of the valid range of items, and then when you go left or right, simply modify that range accordingly.

Let’s assume **int** for now, since it’s easy to conceptualize. And further, let’s assume that **int.MinValue < x < int.MaxValue** just for simplicity sake.

Thus, when we examine the root in our example above, we will test **5** against the range **int.MinValue** to **int.MaxValue.** **5** is indeed in this range, so we are good so far. Now, we know the left subtree of **5** must be **<** **5 **and the right subtree of **5** must be **> 5** so we can recursively call our method on the left subtree with the range **int.MinValue** to **5** and on the right subtree with the range **5 **to **int.MaxValue.**

As we continue down, this will refine our range as we branch left and right at each node because at each step, we will pass in the **min** and **max** for the range, then divide it by the current node.

This gives us the following method (assuming just **int** where **int.MinValue** < **x** < **int.MaxValue**):

public static bool IsBst(Node<int> root, int min = int.MinValue, int max = int.MaxValue)

{

if (root != null)

{

` return root.Data > min && root.Data < max`

? IsBst(root.Left, min, root.Data) && IsBst(root.Right, root.Data, max)

` : false;`

}

return true;

}

If you don’t like that this eliminates **int.MinValue** and **int.MaxValue** from the range, you could have those be **null** to designate the ends:

public static bool IsBst(Node<int> root, int? min = null, int? max = null)

{

if (root != null)

{

` return ((!min.HasValue || root.Data > min) && (!max.HasValue || root.Data < max))`

? IsBst(root.Left, min, root.Data) && IsBst(root.Right, root.Data, max)

` : false;`

}

return true;

}

But we can get even better than that, we could make this method generic so that it can handle any **IComparable. **

Here is the version for reference types:

public static bool IsBst<T>(Node<T> root, T min = null, T max = null) where T : class, IComparable<T>

{

if (root != null)

{

return ((min == null || root.Data.CompareTo(min) > 0) &&

` (max == null || root.Data.CompareTo(max) < 0))`

? IsBst(root.Left, min, root.Data) && IsBst(root.Right, root.Data, max)

` : false;`

}

return true;

}

And for value types (note the need to use nullable types):

public static bool IsBst<T>(Node<T> root, T? min = null, T? max = null) where T : struct, IComparable<T>

{

if (root != null)

{

` return ((!min.HasValue || root.Data.CompareTo(min.Value) > 0) &&`

(!max.HasValue || root.Data.CompareTo(max.Value) < 0))

? IsBst(root.Left, min, root.Data) && IsBst(root.Right, root.Data, max)

` : false;`

}

return true;

}

### Alternative approach: Same thing, but iterative

If you just ** really** hate recursion (aside from the fact you’re using, in essence, a recursive data structure), it is possible to solve this check iteratively.

To do this, you could simply create a queue and push on a small structure containing the node to check and it’s min and max range. You would seed this with the root and null for the min and max, then enter a loop.

For as long as the queue is not empty, check the current node against min and max and if out of order, stop processing. If in order, then push on the children with their modified ranges much like the recursive example. Repeat until queue is empty.

### Alternative approach: In-Order Traversal

As an alternative, you could also perform an in-order traversal on the tree and store each node into a queue, then make a single pass through the queue looking for any item out of place (i.e. any item that is >= the item after it).

### Summary

Hope you had fun with this one! Of course, I’m sure many out there can tweak these answers 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/gB1

Print | posted on Monday, March 30, 2015 12:22 PM | Filed Under [ My Blog C# Software .NET Little Puzzlers ]