How to Solve: Validate Binary Search Tree

How to Solve: Validate Binary Search Tree

Complete Guide for FAANG-Level Interviews

? Introduction

"This problem appears in 1 out of every 3 FAANG onsite interviews—master it, and you prove you can handle recursion, edge cases, and system design constraints in one go."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Validate Binary Search Tree (BST), ensure you understand: 1. Binary Tree Traversal (Inorder, Preorder, Postorder) – BST validation relies on traversal order. 2. Recursion & Stack-Based Iteration – Both are used to traverse trees efficiently. 3. Range-Based Validation – A BST node must satisfy min < node.val < max constraints.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow this repeatable approach for any BST validation problem:

1. Understand BST Definition
2. Left subtree values < node value.
3. Right subtree values > node value.

4. No duplicates (unless specified otherwise).

5. Choose a Traversal Strategy

6. Recursive DFS (Top-Down): Pass min and max bounds.
7. Iterative DFS (Inorder): Check if traversal is strictly increasing.

8. Morris Traversal: If O(1) space is required.

9. Handle Edge Cases

10. Empty tree (root == null) → Valid BST.
11. Single node → Valid BST.

12. All left/right nodes → Check bounds.

13. Implement Bounds Checking (Recursive DFS)

14. For each node, ensure min < node.val < max.

15. Update min for right subtree, max for left subtree.

16. Test with Examples

17. Valid BST: [2,1,3]
18. Invalid BST: [5,1,4,null,null,3,6] (4 is in the wrong place)

19. Edge Case: [1] (single node)

20. Optimize for Time & Space

21. Time: O(N) (visit every node once).
22. Space: O(N) (recursion stack) or O(1) (Morris traversal).

✅ WORKED EXAMPLES

Example 1 – Basic (Recursive DFS)

Problem: Validate BST using recursive bounds checking.

Thought Process: 1. Start with root, min=-∞, max=+∞. 2. For each node, check min < node.val < max. 3. Recurse left with max = node.val. 4. Recurse right with min = node.val.

Python Code:

def isValidBST(root):

    def validate(node, min_val=float('-inf'), max_val=float('inf')):

        if not node:

            return True

        if not (min_val < node.val < max_val):

            return False

        return (validate(node.left, min_val, node.val) and

                validate(node.right, node.val, max_val))


    return validate(root)

Time Complexity: O(N) (visit every node once). Space Complexity: O(N) (recursion stack).

Why This Works: - Each node’s value is checked against dynamically updated bounds. - Left subtree must be < parent, right subtree must be > parent.

Example 2 – Medium (Iterative Inorder Traversal)

Problem: Validate BST using iterative inorder traversal (avoids recursion stack overflow).

Thought Process: 1. Perform inorder traversal (left → root → right). 2. Track prev node and ensure prev.val < current.val. 3. If any violation, return False.

Python Code:

def isValidBST(root):

    stack = []

    prev = None

    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

Time Complexity: O(N). Space Complexity: O(N) (stack space).

Why This Works: - Inorder traversal of a BST yields strictly increasing values. - If any value is ≤ previous, the tree is invalid.

Example 3 – Hard (Follow-Up: O(1) Space with Morris Traversal)

Problem: Validate BST with O(1) space (no recursion, no stack).

Thought Process: 1. Use Morris Traversal to traverse inorder without extra space. 2. Thread the tree by temporarily modifying pointers. 3. Compare prev and current nodes during traversal.

Python Code:

def isValidBST(root):

    prev = None

    current = root

    while current:

        if not current.left:

            if prev and prev.val >= current.val:

                return False

            prev = current

            current = current.right

        else:

            predecessor = current.left

            while predecessor.right and predecessor.right != current:

                predecessor = predecessor.right

            if not predecessor.right:

                predecessor.right = current

                current = current.left

            else:

                predecessor.right = None

                if prev and prev.val >= current.val:

                    return False

                prev = current

                current = current.right

    return True

Time Complexity: O(N). Space Complexity: O(1).

Why This Works: - Morris Traversal temporarily modifies the tree to traverse inorder. - No extra space is used (unlike recursion/stack).

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. To validate a BST, remember three things:

1. BST Definition: Left subtree < node < right subtree (no duplicates unless specified).
2. Traversal Choice:
3. Recursive DFS (easiest, but O(N) space).
4. Iterative Inorder (avoids recursion stack).
5. Morris Traversal (O(1) space, but tricky).
6. Bounds Checking: For every node, ensure min < node.val < max, updating bounds as you recurse.

Edge cases? Empty tree is valid. Single node is valid. All left or all right? Check bounds. Time complexity? O(N). Space? O(N) for recursion, O(1) for Morris.

Now go crush that interview—you’ve got this!

? Final Notes

• Practice Variations:
• BST with duplicates (left ≤ node < right).
• Validate BST in a serialized string (e.g., LeetCode 98).
• Kth smallest element in BST (uses inorder traversal).
• Mock Interview Questions:
• "How would you validate a BST if the tree is stored in an array?"
• "Can you validate a BST without recursion?"

Now go implement this 3 times—once recursively, once iteratively, and once with Morris Traversal. ?