98.Validate_Binary_Search_Tree_(Medium).md

98. Validate Binary Search Tree (Medium)

Date and Time: Jun 9, 2024, 1:32 AM (EST)

Link: https://leetcode.com/problems/validate-binary-search-tree/

Question:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2, 1, 3]

Output: true

Example 2:

Input: root = [5, 1, 4, null, null, 3, 6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

Edge case:

Input: [2, 2, 2]

Output: false

Explanation: The left subtree's value and the right subtree's value should be less than and greater than the root's value.

My Solution:

We know the property of BST that the DFS In-order traversal of BST will create an ascending list, so left.val < root.val < right.val. Hence, we can use global variable prev to keep track of the previous node.val, and we update prev to be current node for next comparison. If prev.val >= node.val, it violates BST and we set res = False and return False.

# 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
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev, res = None, True
        def dfs(node):
            nonlocal prev, res
            if not node:
                return
            dfs(node.left)
            if prev:
                if prev.val >= node.val:
                    res = False
                    return False
            prev = node
            dfs(node.right)
        dfs(root)
        return res

Time Complexity: $O(n)$, because we loop over all the nodes in the worst case, this is not BST for searching.
Space Complexity: $O(1)$

Alternative Solution:

This is also similar to non-recursive dfs implementation. First, iteratively add all the left subtree into stack, then we pop the latest added node and save it as prev and go to its right.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = None
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if prev and prev.val >= root.val:
                return False
            prev = root
            root = root.right
        return True