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.