Problem Description

You are given the root of a binary tree. Your task is to determine whether this tree is a valid Binary Search Tree (BST).

A valid BST must satisfy these properties:

• Every node in the left subtree of a node must have values strictly less than that node's value
• Every node in the right subtree of a node must have values strictly greater than that node's value
• Both the left and right subtrees themselves must also be valid BSTs

The solution uses an in-order traversal approach. During in-order traversal of a valid BST, the nodes are visited in ascending order. The code maintains a variable prev to track the previously visited node's value (initialized to negative infinity). As we traverse:

1. First recursively check the left subtree
2. Then verify the current node's value is greater than prev (ensuring strict ascending order)
3. Update prev to the current node's value
4. Finally recursively check the right subtree

If at any point we find a node whose value is not greater than the previous node's value, we return False. If the entire traversal completes without violations, the tree is a valid BST and we return True.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure, where we have a root node and each node has left and right children.

DFS

• Yes: Since we're dealing with a tree structure, Depth-First Search (DFS) is the natural choice. For validating a BST, we need to traverse the entire tree and check the BST property at every node. DFS allows us to recursively explore each subtree, verifying that all nodes in the left subtree are less than the current node and all nodes in the right subtree are greater.

Conclusion: The flowchart suggests using DFS for this tree problem. The solution implements DFS through an in-order traversal, which visits nodes in the order: left subtree → current node → right subtree. This traversal pattern is perfect for BST validation because a valid BST's in-order traversal produces values in strictly ascending order.

Intuition

The key insight for validating a BST comes from understanding what happens when we traverse a BST in a specific order. If we visit nodes in in-order traversal (left → root → right), a valid BST will always produce values in strictly ascending order. This is because:

1. All values in the left subtree are less than the root
2. All values in the right subtree are greater than the root
3. This property holds recursively for every subtree

Think of it like reading numbers from left to right on a number line - if it's a proper BST, we should always be moving rightward (increasing values) as we traverse.

So instead of checking complex relationships between parent and child nodes throughout the tree, we can simplify the problem: just traverse the tree in-order and check if each value is greater than the previous one. If we ever encounter a value that's not greater than the previous value, we know it's not a valid BST.

This transforms the BST validation problem into a much simpler problem: checking if a sequence is strictly increasing. We use a variable prev to remember the last value we saw (starting at negative infinity since all node values should be greater than it), and during our DFS traversal, we:

• Check the left subtree first (smaller values)
• Compare current node with prev - if current isn't greater, it's not a BST
• Update prev to current value
• Check the right subtree (larger values)

This elegant approach leverages the natural property of in-order traversal on BSTs rather than explicitly checking bounds at each node.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation uses recursive in-order traversal with a global variable to track the previously visited node's value. Here's how the solution works:

Data Structure Used:

• A prev variable initialized to negative infinity (-inf) to store the last visited node's value
• The recursive call stack for DFS traversal

Algorithm Steps:

1. Initialize the tracker: Set prev = -inf as our starting point, ensuring any valid node value will be greater than it.

2. Define the DFS helper function that processes nodes recursively:

   def dfs(root: Optional[TreeNode]) -> bool:

3. Base case: If we reach a None node, return True (an empty tree is a valid BST).

   if root is None:
       return True

4. Traverse left subtree first: Recursively validate the left subtree. If it's invalid, immediately return False.

   if not dfs(root.left):
       return False

5. Check current node: After processing the left subtree, compare the current node's value with prev. If the current value is not strictly greater than prev, the BST property is violated.

   if prev >= root.val:
       return False

6. Update the tracker: Set prev to the current node's value for future comparisons.

   prev = root.val

7. Traverse right subtree: Finally, recursively validate the right subtree.

   return dfs(root.right)

Why This Works:

The nonlocal prev declaration allows the inner function to modify the outer scope's prev variable, maintaining state across recursive calls. As we traverse in-order (left → root → right), we're essentially flattening the tree into a sequence and checking if that sequence is strictly increasing.

The time complexity is O(n) where n is the number of nodes (we visit each node once), and the space complexity is O(h) where h is the height of the tree (for the recursion stack).

Example Walkthrough

Let's validate whether this binary tree is a valid BST:

      5
     / \
    3   8
   / \   \
  2   4   9

We'll track the in-order traversal sequence and check if values are strictly increasing.

Initial State: prev = -inf

Step 1: Start at root (5), go to left subtree first

• Move to node 3

Step 2: From node 3, go to its left subtree

• Move to node 2

Step 3: From node 2, go to its left subtree

• Left is None, return True
• Check current: Is prev (-inf) < 2? Yes ✓
• Update: prev = 2
• Right is None, return True
• Node 2 is valid, backtrack to node 3

Step 4: Back at node 3

• Left subtree (2) was valid
• Check current: Is prev (2) < 3? Yes ✓
• Update: prev = 3
• Now check right subtree (4)

Step 5: At node 4

• Left is None, return True
• Check current: Is prev (3) < 4? Yes ✓
• Update: prev = 4
• Right is None, return True
• Node 4 is valid, backtrack to node 3, then to root 5

Step 6: Back at root 5

• Left subtree (3) was valid
• Check current: Is prev (4) < 5? Yes ✓
• Update: prev = 5
• Now check right subtree (8)

Step 7: At node 8

• Left is None, return True
• Check current: Is prev (5) < 8? Yes ✓
• Update: prev = 8
• Check right subtree (9)

Step 8: At node 9

• Left is None, return True
• Check current: Is prev (8) < 9? Yes ✓
• Update: prev = 9
• Right is None, return True
• Node 9 is valid, backtrack through 8 to root

Result: All checks passed! The in-order sequence was: 2, 3, 4, 5, 8, 9 (strictly increasing) → Valid BST

Counter-example: If node 4 was replaced with 6:

      5
     / \
    3   8
   / \   \
  2   6   9

The in-order sequence would be: 2, 3, 6, 5, 8, 9 When we reach node 5, we'd check: Is prev (6) < 5? No! ✗ → Invalid BST

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs an in-order traversal of the binary search tree using depth-first search (DFS). Each node in the tree is visited exactly once during the traversal. The operations performed at each node (comparison with prev value and updating prev) are constant time O(1) operations. Therefore, with n nodes in the tree, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, the binary tree could be completely unbalanced (essentially a linked list), where all nodes are either only left children or only right children. In this scenario, the recursion depth would be n, requiring O(n) space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but we consider the worst-case scenario for space complexity analysis, which gives us O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Infinity Initialization

The most common pitfall is assuming -inf will always be less than any node value. In some implementations or languages, if the tree contains the minimum possible integer value (e.g., -2^31 in a 32-bit system), using -inf might cause comparison issues or overflow problems.

Problem Example:

# If the tree has Integer.MIN_VALUE as a valid node
#       0
#      /
#   -2147483648
# Using -inf might not work correctly in all environments

Solution: Use a wrapper object or None to track whether we've seen a node yet:

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    def inorder(node):
        if not node:
            return True
      
        if not inorder(node.left):
            return False
      
        # Use None to indicate no previous value seen
        nonlocal prev
        if prev is not None and prev >= node.val:
            return False
        prev = node.val
      
        return inorder(node.right)
  
    prev = None  # Start with None instead of -inf
    return inorder(root)

2. Using Global Variable Instead of Nonlocal

Another pitfall is trying to use a regular variable without the nonlocal keyword, which creates a new local variable instead of modifying the outer scope variable.

Problem Example:

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    prev = -inf
  
    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
      
        # This creates a local 'prev' and throws UnboundLocalError
        if prev >= node.val:  # Error: local variable referenced before assignment
            return False
        prev = node.val  # This creates a new local variable
      
        return inorder(node.right)

Solution: Always use nonlocal for variables you need to modify across recursive calls, or use a mutable container:

# Option 1: Use nonlocal (as in the original solution)
nonlocal prev

# Option 2: Use a mutable container
def isValidBST(self, root: Optional[TreeNode]) -> bool:
    prev = [-inf]  # Use a list to make it mutable
  
    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
      
        if prev[0] >= node.val:
            return False
        prev[0] = node.val  # Modify the list element
      
        return inorder(node.right)
  
    return inorder(root)

3. Forgetting to Handle Equal Values

BST requires strict ordering. A common mistake is using > instead of >= in the comparison, which would incorrectly allow duplicate values.

Problem Example:

# Incorrect: allows duplicates
if prev > node.val:  # Wrong! This allows prev == node.val
    return False

# Tree like this would incorrectly pass:
#       5
#      / \
#     3   5  <- Duplicate 5 is not allowed in BST

Solution: Always use >= to ensure strict inequality:

if prev >= node.val:  # Correct: rejects equal values
    return False