LeetCode - validate-binary-search-tree challenge solution
This one is quite nice, and you should know how to play around with trees. The exercise is to validate this is a binary search tree. That means items on the left are smaller than the head, and items on the right are larger than the head. The above rules should be valid all down the tree path.
In the code below you code see several methods and I'll explain each one of them.
First we start with
isValidBST this is our exercise method that will return our solution.
is just a helper that will just check that our node and its children adhere to our rules.
Here is where most of the work happens, and this method will called recuresively .
for each node we will check for the
then we check for min val and that values are correct and do the same for max vals.
If we got to here, we will call the children and make sure to update the min, max for them as well.
class Solution(object): def isValidBST(self, root): return self.isValidBSThelper(root, None, None) def checkBasicNodeVals(self, root): if root is None: return True if root.left and root.left.val >= root.val: return False if root.right and root.right.val <= root.val: return False return None def isValidBSThelper(self, root, min, max): base_result = self.checkBasicNodeVals(root) if base_result is not None: return base_result if min is not None: if root.left and root.left.val <= min: return False if root.right and root.right.val <= min: return False if max is not None: if root.left and root.left.val >= max: return False if root.right and root.right.val >= max: return False return ( self.isValidBSThelper(root.left, min, root.val) and self.isValidBSThelper(root.right, root.val, max) )