Validating a Binary Search Tree

This is one of those problems that deceives you into thinking that you got it and if you're not careful enough you'll make a mistake. The problem is that when deciding if a tree is a binary search tree or not, you not only have to make sure that the left child is lesser than the root and right child larger; you also have to make sure that the left child is lesser than all its ancestors and right child is larger than all its ancestors. To do this we'll at  least need to go through all the nodes. Thus we need a traversal algorithm either recursive or iterative. Both the recursive and the iterative will take up to O(n) space (the call stack for recursive and a stack data structure for iterative).

I'll start with the iterative algorithm, and I'll take as an example the tree below.

Fig. 1 - Simple Binary Search Tree

The idea of the iterative one is that a binary search tree traversed in-order will always output a ordered sequence. So the above tree traversed in-order will look like this: 16, 25, 41, 42, 46, 53, 55, 60, 62, 63, 64, 65, 70, 74. And, as a reminder, this happens because an in-order traversal visits the left branch first, then the root, and only in the end the right child - which, according to the binary search tree property where the left branch is less than the root, and the right one is larger than the root; leads us into a sorted sequence. Having this said, it would be enough for us to maintain the last visited node's value and keep traversing while the current node's value is larger than the node that we traversed last. If not - this is not a sorted sequence, thus definitely not a binary search tree.

The recursive version may be slightly difficult to understand, but it may be clearer in a way of showing how the ancestors are checked against the binary search property. This means that the children of a specific node are always limited by an upper and lower limit, so that a binary search tree can happen. For example, the children on the left branch of node "65" in the picture above have to be less than 65 and greater than 60 in order to conform to the binary search property. But what are the children of the left/right branches of root node? Well, left children of the root node, have to be less than 60 and greater than -infinity, and children on the right, have to be greater than 60 and less than infinity. 

I still prefer the iterative version over the recursive one - it's clean enough and besides in a production environment it may be a better idea to use the iterative version. But anyways here's the code below.