98

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.