LeetCode 98: Validate Binary Search Tree Solution in Python Explained

Problem Statement

In LeetCode 98, you’re given the root of a binary tree. Your task is to return true if it’s a valid BST—satisfying that for each node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater—otherwise, return false. This builds on tree concepts from LeetCode 95: Unique Binary Search Trees II, shifting focus to validation rather than generation.

Constraints

• Number of nodes: 1 <= n <= 10^4
• Node values: -2^31 <= Node.val <= 2^31 - 1

Example

Let’s see some cases:

Copy codeInput: root = [2,1,3]
      2
     / \
    1   3
Output: true
Explanation: Left (1) < 2, Right (3) > 2, valid BST.

Copy codeInput: root = [5,1,4,null,null,3,6]
      5
     / \
    1   4
       / \
      3   6
Output: false
Explanation: Right subtree (4,3,6) has 3 < 4, invalid.

Copy codeInput: root = [1]
Output: true
Explanation: Single node, trivially valid.

These examples show we’re checking BST properties.

Understanding the Problem

How do you solve LeetCode 98: Validate Binary Search Tree in Python? Take root = [2,1,3]. We need to confirm it’s a BST—left (1) < 2, right (3) > 2, true. For [5,1,4,null,null,3,6], 3 < 4 in the right subtree invalidates it. This isn’t a string interleaving task like LeetCode 97: Interleaving String; it’s about tree property validation. We’ll use: 1. Recursive DFS with Range: O(n) time, O(h) space—our best solution. 2. Inorder Traversal: O(n) time, O(h) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Recursive DFS with Range Approach (Primary)

Explanation

Recursive DFS with Range validates the BST by recursively checking each node against a valid range of values—initially infinite, then updated based on the parent’s value. It’s the best solution due to its efficiency, direct enforcement of BST rules, and ability to handle edge cases like integer limits cleanly.

For [2,1,3]:

• Root 2: Range (-∞, ∞), valid.
• Left 1: Range (-∞, 2), valid.
• Right 3: Range (2, ∞), valid.

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: root = [2,1,3]

Goal: Return true.

• Start: Call validate(2, float('-inf'), float('inf')).
• Step 1: node = 2.
• 2 in (-∞, ∞), true.
• Left: validate(1, -∞, 2).
• 1 in (-∞, 2), true, no children.
• Right: validate(3, 2, ∞).
• 3 in (2, ∞), true, no children.
• Finish: Return true.

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

Goal: Return false.

• Start: validate(5, -∞, ∞).
• Step 1: node = 5, valid.
• Left: validate(1, -∞, 5), valid, no children.
• Right: validate(4, 5, ∞).
• 4 in (5, ∞), false (4 < 5), stop.
• Finish: Return false.

Example 3: root = [1]

Goal: Return true.

• Start: validate(1, -∞, ∞).
• Step 1: node = 1, valid, no children.
• Finish: Return true.

How the Code Works (Recursive DFS with Range) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root: TreeNode) -> bool:
    # Line 1: Define helper function with range
    def validate(node: TreeNode, min_val: float, max_val: float) -> bool:
        # node = current node, min_val = lower bound, max_val = upper bound
        # e.g., node=2, min_val=-∞, max_val=∞ initially

        # Line 2: Base case - empty node
        if not node:
            # If node is None (e.g., left of 1), valid by default
            return True

        # Line 3: Check if node value is within range
        if node.val <= min_val or node.val >= max_val:
            # If value violates bounds (e.g., 4 ≤ 5 for right of 5), invalid
            # Uses <= and >= to handle duplicates (BST requires strict <, >)
            return False

        # Line 4: Validate left subtree
        left_valid = validate(node.left, min_val, node.val)
        # Recursively checks left child with updated max (e.g., max=2 for left=1)
        # Ensures all left values < current node

        # Line 5: Validate right subtree
        right_valid = validate(node.right, node.val, max_val)
        # Recursively checks right child with updated min (e.g., min=2 for right=3)
        # Ensures all right values > current node

        # Line 6: Combine results
        return left_valid and right_valid
        # True only if both subtrees are valid (e.g., both true for [2,1,3])

    # Line 7: Start validation from root
    return validate(root, float('-inf'), float('inf'))
    # Initiates with full range (-∞, ∞) to cover all integer values
    # Returns final validity (e.g., true for [2,1,3])

This detailed breakdown clarifies how the range-based DFS ensures BST validity efficiently.

Alternative: Inorder Traversal Approach

Explanation

Inorder Traversal leverages the BST property that an inorder traversal (left, root, right) yields a strictly increasing sequence. Track the previous value during traversal; if any value isn’t greater, it’s invalid. This is a clever alternative, using traversal order to validate.

For [2,1,3]:

• Inorder: 1, 2, 3 (increasing, valid).

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

• Inorder: 1, 5, 3 (not increasing, invalid).

Step-by-Step Example (Alternative)

For [2,1,3]:

• Start: prev = -∞, result = true.
• Step 1: Left 1, prev=-∞, 1 > -∞, prev=1.
• Step 2: Root 2, 2 > 1, prev=2.
• Step 3: Right 3, 3 > 2, prev=3.
• Finish: Return true.

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

• Step: 1, 5, 3 (3 ≤ 5, false).
• Finish: Return false.

How the Code Works (Inorder Traversal)

Copy codedef isValidBSTInorder(root: TreeNode) -> bool:
    prev = [float('-inf')]
    def inorder(node: TreeNode) -> bool:
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)
    return inorder(root)

Complexity

• Recursive DFS with Range:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Inorder Traversal:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack.

Efficiency Notes

Recursive DFS with Range is the best solution with O(n) time and O(h) space, offering a direct, robust approach that handles edge cases like integer bounds—Inorder Traversal is elegant and matches complexity but relies on traversal order, making it a strong alternative.

Key Insights

• Range Check: Enforces BST rules.
• Inorder Property: Increasing sequence.
• Edge Values: Handle min/max integers.

Additional Example

For root = [10,5,15,null,null,6,20]:

• Goal: false.
• DFS: Right of 10, 6 < 15 → false.

Edge Cases

• Single Node: [1] → true.
• Duplicates: [1,1] → false.
• Max Int: [2^31-1] → true.

Both solutions handle these well.

Final Thoughts

LeetCode 98: Validate Binary Search Tree in Python is a key BST validation challenge. The Recursive DFS with Range solution stands out for its efficiency and clarity, while Inorder Traversal offers a clever twist. Want more? Try LeetCode 95: Unique Binary Search Trees II for tree generation or LeetCode 94: Binary Tree Inorder Traversal for traversal basics. Ready to practice? Solve LeetCode 98 on LeetCode with [2,1,3], aiming for true—test your skills now!