Leetcode: Validate Binary Search Tree
Given the 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 left
and 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 max(lower, node.value)
.
Using float('-inf')
and 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.