This “medium” problem does present a nice way where an initial solution (i.e., mine) has lots of room for improvement. Assuming the student knows what a binary search tree is and is fairly comfortable with them, and recursion, this is an excellent homework problem. In a sense, it’s taking the invariants of a binary search tree, and taking them a step further and applying them to solve a new problem, validation. While this is a bit contrived, I think validation for a datastructure has good-enough motivation.
The solution code is a bit bigger than typical, and I bet it can be made a lot smaller and more efficient. I just was confident this would work, so I went that way. An opportunity, later, to discuss how to improve code after-the-fact?
Solution Ideas
- All nodes to the left of our “root” (and remember we’re going to look at every node as its own root) should be smaller than us. So we’d like to know what the largest value to our left is—if we’re bigger than that, then we’re OK. Similarly, we want to know the smallest value to our right [Note: terrifyingly, as I was writing this, the “we want to know the smallest value to…” auto-complete filled in “to our right”! I suppose it saw the opposites of larger and smallest, and mapped that to right/left? Spooky!].
- So I imagined as if I knew the min-and-max values for each node. If we had that attached to each node, we can simply query our immediate children and see what they each have as their min/max values. If our value is smaller than the max of our left, or larger than the min of our right, we are not a valid BST.
- Additionally, if we have the min/max values of our children, we can easily compute the min/max values of ourselves.
Finding the min or max value of a tree is an easy-enough recursive exercise. Doing both at the same time is a nice sequel. Doing it for all node is itself an interesting problem: I haven’t done out the arithmetic, but the temptation to do it “purely recursively” would lead to a very expensive algorithm. I don’t know if it’s quadratic per-se, but it sounds like “for each node, walk the tree”. So you want a very deliberate bottom-up approach.
Conclusion
My solution is a bit of a hybrid where I set the stage for a two-pass approach, computing global maps for the nodes, but then realized I could determine a BST violation while computing the maps. I bet we can get rid of the maps and turn this into a more typical recursive formulation. Later!
class Solution:
def solution(self, root):
if root is None:
self.minMap[root] = None
self.maxMap[root] = None
return True
l = self.solution(root.left)
if not l: return False # might as well stop
r = self.solution(root.right)
if not r: return False
lm = self.maxMap[root.left]
if lm is not None and lm >= root.val:
return False
rm = self.minMap[root.right]
if rm is not None and rm <= root.val:
return False
rMax = self.maxMap[root.right]
if rMax is None:
rMax = root.val
lMin = self.minMap[root.left]
if lMin is None:
lMin = root.val
self.maxMap[root] = rMax
self.minMap[root] = lMin
return True
def isValidBST(self, root: Optional[TreeNode]) -> bool:
# Observation: if we check each node, we'll be doing something that feels
# a little bit too "quadratic" (for each node, validate the rest of the tree)
# What we can do is build a map of nodes to min/max values under that tree,
# and then do another pass (in parallel?) to do the final validation.
# So, in other words:
# Silly initializatio
self.minMap = {}
self.maxMap = {}
return self.solution(root)
More BST questions can be found here.
