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.
2
/ \
1 55. 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).
3
/ \
1 5
/ \
2 9float('-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.
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self) -> str:
"""Convenience function for easy debugging"""
return str(self.val)
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root is None:
return None
def inner(root, lt=None, gt=None):
if root is None:
return True
if root.val <= lt or root.val >= gt:
return False
left = inner(root.left, lt=lt, gt=min(gt, root.val))
right = inner(root.right, lt=max(lt, root.val), gt=gt)
return left and right
return inner(root, float('-inf'), float('inf'))
if __name__ == '__main__':
s = Solution().isValidBST
t1 = TreeNode(2, TreeNode(1), TreeNode(3))
print(s(t1), True)
t2 = TreeNode(5, None, TreeNode(7, TreeNode(4)))
print(s(t2), False)
t3 = TreeNode(0, None, TreeNode(-1))
print(s(t3), False)
t4 = TreeNode(32, TreeNode(26, TreeNode(19, None, None), TreeNode(47, None, TreeNode(56, None, TreeNode(27)))))
print(s(t4), False)
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.