Firstly, understand what is a BST. Convention has it that the left child must always be smaller for the right child, for the entire tree. Here is an illustration.
There are a few conditions, and informally:
- left child node is always lesser than parent node and right child node is always greater than parent node
- check the nodes ancestry from the root whether the above rule held up for all the parent-child relationships. For instance, you can’t have 19 as left child node of node with value 25. This is because it would have failed the check at node with value 20.
With the concept of BST out of the way, let’s find out how to validate one. In essence, you would need 2 variables to set the lower and upper limit each time you proceed down the tree. In our case, we shall use pre-order traversal. This just means we look at parent node, then look at left child, then look at right child.
We first start with negative infinity to infinity. As we move down the tree, we start setting new boundaries. If it is a left node, we set the reset the upper boundary. If it is a right node, we reset the lower boundary. The reasons can be easily inferred from the above diagram.
Here is the python implementation
Now let’s discuss the time and space complexity of this implementation.
Time complexity: if we have n nodes, we look at each of them plus, we also look at all the None nodes after the leafs for our base conditions. Assuming we have k Nones, then time complexity would be O(n+k) ≈ O(n)
Space complexity: my stack frame will only be has tall has the tree levels, since we are always popping. So if the tree is k height and since we have 3 variables (node,lower,upper), we have O(3k) ≈ O(n)
Happy coding.
