066.md

98. Validate Binary Search Tree

Difficulty: 🟡 Medium

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  of a node contains only nodes with keys less than the node's key.

  subtree

• 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.

Examples:

Example 1:

![066_01.jpg][./resources/066_01.jpg]

Input: root = [2,1,3]
Output: true

Example 2:

![066_02.jpg][./resources/066_02.jpg]

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.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 231 <= Node.val <= 231 - 1

Solutions

O(n) solution

Python 3

# 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:
        last, stack = None, []
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            
            curr = stack.pop()

            if last is not None and last >= curr.val:
                return False

            last = curr.val
            curr = curr.right

        return True

The given solution provides an iterative approach to determine if a binary tree is a valid BST.

Here is an overview of the solution:

1. Initialize a variable last to keep track of the last visited value during the inorder traversal. Set it to None.
2. Initialize an empty stack called stack.
3. Set a current node curr to the root of the binary tree.
4. While curr is not None or stack is not empty, do the following:
   • While curr is not None, push curr onto stack and update curr to curr's left child. This step traverses to the leftmost node of the current subtree.
   • Pop the top node curr from stack and check if its value is less than or equal to last. If it is, return False as it violates the BST property.
   • Update last to the value of the popped node.
   • Set curr to the right child of the popped node. This step moves to the right child of the current node if it exists.
5. If the traversal completes without returning False, return True, indicating that the binary tree is a valid BST.

The solution performs an inorder traversal of the binary tree using an iterative approach and checks if the values are in ascending order. If any value is greater than or equal to the previous value (last), it returns False, indicating that the binary tree is not a valid BST.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the binary tree. We visit each node once during the inorder traversal.

The space complexity is O(h), where h is the height of the binary tree. In the worst case, the height of the binary tree can be O(n) for a skewed tree, resulting in O(n) space complexity. However, for a balanced tree, the height is O(log n), resulting in O(log n) space complexity.

Summary

The given solution efficiently determines whether a given binary tree is a valid BST using an iterative approach. It performs an inorder traversal of the tree and checks if the values are in ascending order. The solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes in the binary tree and h is the height of the tree.

NB: If you want to get community points please suggest solutions in other languages as merge requests.