< Back





98. Validate Binary Search Tree

We're asked to validate a binary search tree. It's known that if you traverse a binary search tree
using depth-first search, if you process the elements in order, you will access each node in sorted
order. We use this property to check if the previously visited node's value is less than the current
node's value.

The solution is as follows:


  class Solution:
      def isValidBST(self, root: Optional[TreeNode]) -> bool:
          self.prev = float("-inf")

          def dfs(node: Optional[TreeNode]) -> bool:
              if not node:
                  return True
              if not dfs(node.left):
                  return False
              if not self.prev < node.val:
                  return False
              self.prev = node.val
              return dfs(node.right)

          return dfs(root)


_ Time Complexity:

  O(n) - We inspect all nodes in the binary search tree.

_ Space Complexity:

  O(n) - Our call stack can grow as large as the number of nodes in the binary search tree.