#34 · Trees

Validate Binary Search Tree

Given the root of a binary tree, decide whether it is a valid binary search tree: for EVERY node, all values in its left subtree are smaller and all values in its right subtree are larger.

MediumLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary search tree invariant

The rule applies to whole subtrees, not just children: every descendant on the left is smaller than the node, every descendant on the right is larger. It is a statement about ancestors, so a node can break the rule because of a grandparent it never touches directly.

Memory layout

Pointer-linked nodes. The invariant lives in the values, not in the structure.

Operation	Cost
validate	O(n) time (every node must be examined)
extra space	O(h) recursion/stack, or O(1) with Morris

In-order traversal

Visiting left subtree, node, right subtree prints a BST in sorted order. So "is it a BST?" is equivalent to "is the in-order sequence strictly increasing?", which only needs the previously visited value.

Memory layout

A stack of ancestors (explicit, or the call stack), or threads in Morris traversal.

Operation	Cost
in-order walk	O(n) time

Valid window (lo, hi)

Alternative view: each node inherits an open interval from its ancestors. The left child keeps lo and takes the parent as its new hi; the right child keeps hi and takes the parent as lo. A node is valid if its value lies strictly inside its interval.

Memory layout

Two numbers passed down each recursive call.

Operation	Cost
check a node	O(1)

Why it fits

The BST property is global (it involves all ancestors), so comparing each node only with its children is wrong: it accepts trees like 10 → (5, 15 → (6, 20)).
In-order order and (lo, hi) windows are two faces of the same invariant: either carry the previous value, or carry the interval from the ancestors.
Both visit each node once, so O(n) is optimal: any single node could be the one that is out of place.

Why alternatives degrade

Compare each node with its two children only:: Misses violations caused by a farther ancestor, e.g. 6 under 15 under 10: 6 < 15 looks fine but 6 < 10 is illegal in the right subtree of 10.
Check only that the left child < node < right child recursively:: Same flaw: the check never remembers the ancestors' limits.
Non-strict comparisons (≤ / ≥):: A BST by this problem has distinct keys per side: equal values on either side are invalid, so use strict < and >.

Four approaches, from naive to production

1 · beginner

In-order list, then check it

time O(n)space O(n)

Collect the in-order values into an array and verify that the array is strictly increasing.

bool isValidBST(TreeNode* root) {
    vector<long long> values;
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        values.push_back(node->val);
        inorder(node->right);
    };
    inorder(root);
    for (size_t i = 1; i < values.size(); i++) {
        if (values[i] <= values[i - 1]) return false;
    }
    return true;
}

public boolean isValidBST(TreeNode root) {
    List<Integer> values = new ArrayList<>();
    inorder(root, values);
    for (int i = 1; i < values.size(); i++) {
        if (values.get(i) <= values.get(i - 1)) return false;
    }
    return true;
}

private void inorder(TreeNode node, List<Integer> values) {
    if (node == null) return;
    inorder(node.left, values);
    values.add(node.val);
    inorder(node.right, values);
}

def is_valid_bst(root):
    values = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        values.append(node.val)
        inorder(node.right)
    inorder(root)
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]: return False
    return True

function isValidBST(root: TreeNode | null): boolean {
  const values: number[] = [];
  const inorder = (node: TreeNode | null): void => {
    if (!node) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  };
  inorder(root);
  for (let i = 1; i < values.length; i++) {
    if (values[i] <= values[i - 1]) return false;
  }
  return true;
}

Flaws & bottlenecks

Stores all n values even though only the previous one is ever needed.
Always walks the whole tree before checking anything, so an early violation is found late.
Two passes (build, then check).

Interviewer cross-questions

Why does a sorted in-order list prove validity?

Say: The in-order sequence of a BST is sorted by construction, and the converse holds too: if the in-order sequence is strictly increasing, every left descendant precedes (is smaller than) the node and every right descendant follows it.

Why strictly increasing?

Say: Duplicates are not allowed on either side of a node in this problem, so equal consecutive values mean the tree is invalid.

How can you stop earlier and save memory?

Say: Keep only the previously visited value and compare while traversing: iterative in-order with early exit.

2 · intermediate

Recursion with (lo, hi) bounds

time O(n)space O(h)

Pass the allowed open interval down: the left child may not reach the parent, the right child may not drop to it. A node outside its interval makes the whole tree invalid.

bool isValidBST(TreeNode* root) {
    function<bool(TreeNode*, long long, long long)> check = [&](TreeNode* node, long long lo, long long hi) -> bool {
        if (!node) return true;
        if (node->val <= lo || node->val >= hi) return false;
        return check(node->left, lo, node->val) && check(node->right, node->val, hi);
    };
    return check(root, LLONG_MIN, LLONG_MAX);
}

public boolean isValidBST(TreeNode root) {
    return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean check(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
}

def is_valid_bst(root):
    def check(node, lo, hi):
        if not node: return True
        if node.val <= lo or node.val >= hi: return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)
    return check(root, float('-inf'), float('inf'))

function isValidBST(root: TreeNode | null): boolean {
  const check = (node: TreeNode | null, lo: number | null, hi: number | null): boolean => {
    if (!node) return true;
    if ((lo !== null && node.val <= lo) || (hi !== null && node.val >= hi)) return false;
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
  };
  return check(root, null, null);
}

Flaws & bottlenecks

Uses null for "no limit", so the checks need care; extreme values (INT_MIN/INT_MAX) break the common shortcut of using them as sentinels.
Recursion depth equals tree height.
The bounds are implicit state that is easy to pass in the wrong order (swapping lo and hi).

Interviewer cross-questions

Why use null (or infinity) instead of INT_MIN / INT_MAX for the initial bounds?

Say: A node can legitimately hold INT_MIN or INT_MAX. A sentinel equal to a real value would reject a valid tree. "No limit" must be a separate state (null or ±infinity).

Why is it enough to look at only the direct parent when passing the window?

Say: The child inherits the parent's window and tightens exactly one side with the parent's value. So the window already contains every ancestor's constraint.

What is the difference from checking children only?

Say: Children-only forgets the grandparent's limits. The window carries them downward, so a node deep in the right subtree is still compared with a distant ancestor.

3 · advanced

Iterative in-order, previous value

time O(n)space O(h)

Walk the tree in order with an explicit stack and remember only the previous value. The first time a value does not exceed its predecessor, return false.

bool isValidBST(TreeNode* root) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    bool hasPrev = false; long long prev = 0;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back(); stack.pop_back();
        if (hasPrev && node->val <= prev) return false;
        hasPrev = true; prev = node->val;
        node = node->right;
    }
    return true;
}

public boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    Long prev = null;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        if (prev != null && node.val <= prev) return false;
        prev = (long) node.val;
        node = node.right;
    }
    return true;
}

def is_valid_bst(root):
    stack = []
    node = root
    prev = None
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and node.val <= prev: return False
        prev = node.val
        node = node.right
    return True

function isValidBST(root: TreeNode | null): boolean {
  const stack: TreeNode[] = [];
  let node = root;
  let prev: number | null = null;
  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    if (prev !== null && node.val <= prev) return false;
    prev = node.val;
    node = node.right;
  }
  return true;
}

Flaws & bottlenecks

Stack memory is the tree height, O(n) for a chain.
The loop with an inner loop and a null check is easy to write wrong.
Modifies nothing, but needs null as a "no previous value yet" state, which fails if you use a sentinel number.

Interviewer cross-questions

Why can it stop at the first violation?

Say: In-order visits in ascending order for a valid tree, so the first descent already proves invalidity: no later value can repair it.

Why is prev nullable rather than −infinity?

Say: A tree may legitimately contain the smallest integer. A real "nothing visited yet" state avoids rejecting it.

Compare with the recursive bounds solution.

Say: Same O(n) time and O(h) space. The iterative version exits early on the first out-of-order pair without the recursion, and it cannot overflow the call stack on a deep tree.

4 · expert

Morris in-order (O(1) space)

time O(n)space O(1)

In-order traversal with no stack: temporarily make each left subtree's rightmost node point back at its ancestor (a thread), follow it to climb back, and remove it. Record a violation in a flag instead of returning early so the tree is always restored.

bool isValidBST(TreeNode* root) {
    bool valid = true;
    bool hasPrev = false; long long prev = 0;
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            if (hasPrev && cur->val <= prev) valid = false;
            hasPrev = true; prev = cur->val;
            cur = cur->right;
        } else {
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur) pred = pred->right;
            if (!pred->right) {
                pred->right = cur;
                cur = cur->left;
            } else {
                pred->right = nullptr;
                if (hasPrev && cur->val <= prev) valid = false;
                hasPrev = true; prev = cur->val;
                cur = cur->right;
            }
        }
    }
    return valid;
}

public boolean isValidBST(TreeNode root) {
    boolean valid = true;
    Long prev = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            if (prev != null && cur.val <= prev) valid = false;
            prev = (long) cur.val;
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;
                cur = cur.left;
            } else {
                pred.right = null;
                if (prev != null && cur.val <= prev) valid = false;
                prev = (long) cur.val;
                cur = cur.right;
            }
        }
    }
    return valid;
}

def is_valid_bst(root):
    valid = True
    prev = None
    cur = root
    while cur:
        if not cur.left:
            if prev is not None and cur.val <= prev: valid = False
            prev = cur.val
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur: pred = pred.right
            if not pred.right:
                pred.right = cur
                cur = cur.left
            else:
                pred.right = None
                if prev is not None and cur.val <= prev: valid = False
                prev = cur.val
                cur = cur.right
    return valid

function isValidBST(root: TreeNode | null): boolean {
  let valid = true;
  let prev: number | null = null;
  let cur = root;
  while (cur) {
    if (!cur.left) {
      if (prev !== null && cur.val <= prev) valid = false;
      prev = cur.val;
      cur = cur.right;
    } else {
      let pred = cur.left;
      while (pred.right && pred.right !== cur) pred = pred.right;
      if (!pred.right) {
        pred.right = cur;
        cur = cur.left;
      } else {
        pred.right = null;
        if (prev !== null && cur.val <= prev) valid = false;
        prev = cur.val;
        cur = cur.right;
      }
    }
  }
  return valid;
}

Flaws & bottlenecks

Mutates the tree while running, so it is unsafe with concurrent readers and must always finish to restore the threads.
Cannot exit early on the first violation (it would leave threads behind), so invalid trees cost as much as valid ones.
Harder to read and to verify than the stack-based version.

Interviewer cross-questions

Why not return false at the first violation?

Say: Threads are temporary pointers inside the tree. Returning early would leave some of them in place and corrupt the caller's tree. We record valid = false and let the traversal finish, removing every thread.

How does the thread give O(1) space?

Say: It is the "return address" that a stack would otherwise store: the rightmost node of the left subtree points back at the ancestor, so after finishing that subtree the walk can climb back without remembering anything.

When is this worth it?

Say: When memory is extremely constrained or the tree is far too deep for the call stack and an explicit stack is unacceptable. Otherwise prefer the simpler iterative in-order.

Synchronized code walkthrough

Showing: In-order list, then check it — shares the player above; click any step to jump.

bool isValidBST(TreeNode* root) {
    vector<long long> values;
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        values.push_back(node->val);
        inorder(node->right);
    };
    inorder(root);
    for (size_t i = 1; i < values.size(); i++) {
        if (values[i] <= values[i - 1]) return false;
    }
    return true;
}

public boolean isValidBST(TreeNode root) {
    List<Integer> values = new ArrayList<>();
    inorder(root, values);
    for (int i = 1; i < values.size(); i++) {
        if (values.get(i) <= values.get(i - 1)) return false;
    }
    return true;
}

private void inorder(TreeNode node, List<Integer> values) {
    if (node == null) return;
    inorder(node.left, values);
    values.add(node.val);
    inorder(node.right, values);
}

def is_valid_bst(root):
    values = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        values.append(node.val)
        inorder(node.right)
    inorder(root)
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]: return False
    return True

function isValidBST(root: TreeNode | null): boolean {
  const values: number[] = [];
  const inorder = (node: TreeNode | null): void => {
    if (!node) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  };
  inorder(root);
  for (let i = 1; i < values.length; i++) {
    if (values[i] <= values[i - 1]) return false;
  }
  return true;
}

bool isValidBST(TreeNode* root) {
    function<bool(TreeNode*, long long, long long)> check = [&](TreeNode* node, long long lo, long long hi) -> bool {
        if (!node) return true;
        if (node->val <= lo || node->val >= hi) return false;
        return check(node->left, lo, node->val) && check(node->right, node->val, hi);
    };
    return check(root, LLONG_MIN, LLONG_MAX);
}

public boolean isValidBST(TreeNode root) {
    return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean check(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
}

def is_valid_bst(root):
    def check(node, lo, hi):
        if not node: return True
        if node.val <= lo or node.val >= hi: return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)
    return check(root, float('-inf'), float('inf'))

function isValidBST(root: TreeNode | null): boolean {
  const check = (node: TreeNode | null, lo: number | null, hi: number | null): boolean => {
    if (!node) return true;
    if ((lo !== null && node.val <= lo) || (hi !== null && node.val >= hi)) return false;
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
  };
  return check(root, null, null);
}

bool isValidBST(TreeNode* root) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    bool hasPrev = false; long long prev = 0;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back(); stack.pop_back();
        if (hasPrev && node->val <= prev) return false;
        hasPrev = true; prev = node->val;
        node = node->right;
    }
    return true;
}

public boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    Long prev = null;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        if (prev != null && node.val <= prev) return false;
        prev = (long) node.val;
        node = node.right;
    }
    return true;
}

def is_valid_bst(root):
    stack = []
    node = root
    prev = None
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and node.val <= prev: return False
        prev = node.val
        node = node.right
    return True

function isValidBST(root: TreeNode | null): boolean {
  const stack: TreeNode[] = [];
  let node = root;
  let prev: number | null = null;
  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    if (prev !== null && node.val <= prev) return false;
    prev = node.val;
    node = node.right;
  }
  return true;
}

bool isValidBST(TreeNode* root) {
    bool valid = true;
    bool hasPrev = false; long long prev = 0;
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            if (hasPrev && cur->val <= prev) valid = false;
            hasPrev = true; prev = cur->val;
            cur = cur->right;
        } else {
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur) pred = pred->right;
            if (!pred->right) {
                pred->right = cur;
                cur = cur->left;
            } else {
                pred->right = nullptr;
                if (hasPrev && cur->val <= prev) valid = false;
                hasPrev = true; prev = cur->val;
                cur = cur->right;
            }
        }
    }
    return valid;
}

public boolean isValidBST(TreeNode root) {
    boolean valid = true;
    Long prev = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            if (prev != null && cur.val <= prev) valid = false;
            prev = (long) cur.val;
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;
                cur = cur.left;
            } else {
                pred.right = null;
                if (prev != null && cur.val <= prev) valid = false;
                prev = (long) cur.val;
                cur = cur.right;
            }
        }
    }
    return valid;
}

def is_valid_bst(root):
    valid = True
    prev = None
    cur = root
    while cur:
        if not cur.left:
            if prev is not None and cur.val <= prev: valid = False
            prev = cur.val
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur: pred = pred.right
            if not pred.right:
                pred.right = cur
                cur = cur.left
            else:
                pred.right = None
                if prev is not None and cur.val <= prev: valid = False
                prev = cur.val
                cur = cur.right
    return valid

function isValidBST(root: TreeNode | null): boolean {
  let valid = true;
  let prev: number | null = null;
  let cur = root;
  while (cur) {
    if (!cur.left) {
      if (prev !== null && cur.val <= prev) valid = false;
      prev = cur.val;
      cur = cur.right;
    } else {
      let pred = cur.left;
      while (pred.right && pred.right !== cur) pred = pred.right;
      if (!pred.right) {
        pred.right = cur;
        cur = cur.left;
      } else {
        pred.right = null;
        if (prev !== null && cur.val <= prev) valid = false;
        prev = cur.val;
        cur = cur.right;
      }
    }
  }
  return valid;
}