LeetCode 98: Validate Binary Search Tree

Validating a Binary Search Tree (BST) is a classic interview question that tests your grasp of tree properties. While it might seem as simple as checking if each node's left child is smaller and right child is larger, there's a global constraint that often trips up candidates. 🌳

🧩 The Problem

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 strictly less than the node's key.

The right subtree of a node contains only nodes with keys strictly greater than the node's key.

Both the left and right subtrees must also be binary search trees.

Example

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 (which is less than 5).

🛠️ Approach: Iterative Inorder Traversal

The Insight

A key property of a Binary Search Tree is that its inorder traversal (Left -> Node -> Right) visits nodes in strictly increasing order.

If we perform an inorder traversal and keep track of the prev node's value, we can simply verify that every current node's value is greater than the previous one. If we ever find a node where curr.val <= prev, the BST property is violated.

Why Iterative?

While recursion is intuitive for trees, an iterative approach using a Stack avoids potential stack overflow issues for very deep trees and allows us to stop the traversal immediately as soon as a violation is found.

🔍 Visualizing the Approach (Dry Run)

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

Step	Node	Stack	Prev Value	Action / Logic
1	5	`[5]`	`-inf`	Move left to 1
2	1	`[5, 1]`	`-inf`	Move left (null)
3	1	`[5]`	`1`	Pop 1, update `prev = 1`, move right (null)
4	5	`[]`	`5`	Pop 5, update `prev = 5`, move right to 4
5	4	`[4]`	`5`	Move left to 3
6	3	`[4, 3]`	`5`	Move left (null)
7	3	`[4]`	`5`	Pop 3. Validation: 3 <= 5? YES. Return `False` ❌

💻 Code Implementation

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        stack = []
        prev = float('-inf')
        curr = root
        
        while stack or curr:
            # 1. Reach the leftmost node of the current subtree
            while curr:
                stack.append(curr)
                curr = curr.left
            
            # 2. Process the node
            curr = stack.pop()
            
            # If current value is not strictly greater than prev, it's invalid
            if curr.val <= prev:
                return False
            
            prev = curr.val
            
            # 3. Move to the right subtree
            curr = curr.right
        
        return True

⏱️ Complexity Analysis

Complexity	Rating	Description
Time	$O(N)$	In the worst case (a valid BST), we visit every node exactly once.
Space	$O(N)$	The stack can store up to $N$ nodes in the case of a skewed tree.

🧠 How to Recognize This Pattern

This "Inorder Traversal for BST Properties" pattern is extremely useful for:

Kth Smallest Element in a BST: Perform inorder traversal and stop at the $k$ -th node.
Inorder Successor in BST: Find the next node in the traversal.
Recover Binary Search Tree: Find two swapped nodes using inorder traversal violations.

🎯 Interview Tips

The "Local vs Global" Trap: Be careful! A common mistake is only checking if node.left.val < node.val < node.right.val. This isn't enough—every node in the left subtree must be less than the root.
Handle Edge Cases: Ask the interviewer if the tree can have duplicate values. In a standard BST, values are usually strictly increasing, so curr.val <= prev is the correct check.
Space Trade-offs: Mention that while the iterative approach uses $O(H)$ space (where $H$ is height), a Morris Traversal could achieve $O(1)$ space, though it's much more complex to implement.

Leetcode 98 Validate Binary Search Tree