Friedrich Ewald My Personal Website

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.

    / \
   1   5
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).
    / \
   1   5
      / \
     2   9
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.
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.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.