Validate Binary Search Tree

The problem description can be found in LeetCode.

Approach

The solution is in the question itself. It already collects all the three checks we need to perform in the problem description.

So, once we checked the correctness of the root, left and right values, we start checking all the other sub-trees.

Solution

from typing import Optional


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(
            root: Optional[TreeNode], lower_bound: float, upper_bound: float
        ) -> bool:
            if not root:
                return True
            if not (lower_bound < root.val < upper_bound):
                return False

            return dfs(root.left, lower_bound, root.val) and dfs(
                root.right, root.val, upper_bound
            )

        return dfs(root, float("-inf"), float("+inf"))

Complexity

• Time: $O(n)$
• Space: $O(h)$

Where $n$ is the number of nodes in the tree and $h$ is its height. If the tree is unbalanced, it is like having a Linked List, hence $h=n$.