Practice/Amazon/Leetcode 98. Validate Binary Search Tree

Leetcode 98. Validate Binary Search Tree

CodingOptional

Problem

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

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with values strictly less than the node's value
• The right subtree of a node contains only nodes with values strictly greater than the node's value
• Both the left and right subtrees must also be valid binary search trees

Note that these conditions must hold globally across the entire tree, not just for immediate children. For example, all nodes in the left subtree must be less than the root, not just the immediate left child.

Requirements

1. Implement a function that takes the root of a binary tree as input
2. Return true if the tree is a valid BST, false otherwise
3. Handle edge cases including empty trees and single-node trees
4. Ensure the solution checks the global BST property, not just local parent-child relationships
5. Values must be strictly less than or greater than (duplicates violate the BST property)

Constraints

• The number of nodes in the tree is in the range [0, 10^4]
• -2^31 <= Node.val <= 2^31 - 1
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(h) where h is the height of the tree (for recursion stack)

Examples

Example 1:

Input: root = [5, 3, 8, 1, 4, null, 9] 5 / \ 3 8 / \ \ 1 4 9 Output: true Explanation: Every node satisfies the BST property. All left descendants are smaller and all right descendants are larger.

Example 2:

Input: root = [5, 1, 6, null, null, 4, 7] 5 / \ 1 6 / \ 4 7 Output: false Explanation: Node 4 is in the right subtree of root 5, but 4 < 5, violating the BST property.

Example 3:

Input: root = [2, 2, 3] 2 / \ 2 3 Output: false Explanation: The left child has value 2, which equals the parent. BST requires strict inequality.