Leetcode: Validate Binary Search Tree
root node of a tree, validate whether it is a valid Binary Search Tree. This is a tree where each node is unique, left children are smaller than the root and right children are greater than the root.
Because we’re dealing with a tree, there are two possible algorithms that we can use: DFS and BFS. In this case, I decided to go with a recursive DFS approach. In a simple example we see, that we need to compare the
left child with the
val of the current node. If the
left child is equal or greater than the value of the root node, we can return
False immediately and don’t need to traverse through the rest of the tree. Otherwise, we need to recursively visit the
right children respectively.
If we expand the example above, we now see that we need to check also the children of
5. We then need to compare them to the
root of the tree. In this particular example,
2 is less than
3 and the tree is not a valid binary search tree.
To make the comparison recursively, we can pass ranges to the method in which the value has to be. We start with
[float('-inf'), float('inf')] and update it once we reach the first node. If we go to the left, we know that the upper boundary is now the nodes values. If we go to the right, we set the lower boundary to the
float('inf') respectively is a common way to initialize values in Python that need to get updated iteratively. The end result is the following code.
Runtime: 106 ms, faster than 5.15% of Python3 online submissions for Validate Binary Search Tree. Memory Usage: 16.5 MB, less than 47.01% of Python3 online submissions for Validate Binary Search Tree.