Validate BST

Tags

Validate BST

Category

BST (Binary Search Trees)

Difficulty

Medium

Problem Statement

Given a binary tree, determine whether it is a valid Binary Search Tree. A valid BST has the property that for every node, all nodes in its left subtree have values strictly less than the node's value, and all nodes in its right subtree have values greater than or equal to the node's value.

Intuition

Simply checking that each node's left child is smaller and right child is larger is insufficient — a node deep in the left subtree could violate the BST property relative to an ancestor. The correct approach is to maintain a valid range (min, max) for each node. As we traverse left, we tighten the upper bound; as we traverse right, we tighten the lower bound. Every node must fall within its allowed range.

Approach

  1. Start at the root with an initial range of (-infinity, +infinity).
  2. For each node, check that its value falls within the valid range.
  3. Recurse on the left child with an updated upper bound (current node's value).
  4. Recurse on the right child with an updated lower bound (current node's value).
  5. If any node violates its range, return false. If all nodes pass, return true.

Pseudocode

function validateBST(root):
    return helper(root, -infinity, +infinity)

function helper(node, minValue, maxValue):
    if node is null:
        return true
    if node.value < minValue or node.value >= maxValue:
        return false
    return helper(node.left, minValue, node.value) and
           helper(node.right, node.value, maxValue)

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Every node is checked once.
  • Space: O(h) where h is the height of the tree, due to the recursion stack. O(log n) for balanced, O(n) for skewed.

Key Insights

  • Checking only parent-child relationships is not enough. The range-based approach enforces the BST property globally.
  • The left child must be strictly less than the parent, while the right child must be greater than or equal (or strictly greater, depending on the problem definition).
  • An in-order traversal of a valid BST produces a sorted sequence. This can be an alternative validation approach.
  • Be careful with the boundary convention: does the right subtree allow equal values or not? This must match the BST definition used.

Edge Cases

  • Null/empty tree: considered a valid BST (return true).
  • Single-node tree: always valid.
  • A tree where only the parent-child relationships are correct but a deeper node violates the BST property relative to an ancestor.
  • Trees with duplicate values — ensure the equal-value convention is handled consistently.
  • All nodes have the same value — valid only if they form a right-skewed chain (given the "right >= node" convention).

Linked mentions