Microsoft Practice: Validate Binary Search Tree

Problem

Problem statement

Given the root of a binary tree, return true if it is a valid binary search tree (BST).

In a valid BST, every value in a node’s left subtree is strictly less than the node’s value, every value in its right subtree is strictly greater, and both subtrees are valid BSTs too.

Trees below are written in level order; null marks a missing child.

Examples

Example 1

Input: root = [2, 1, 3]
Output: true

Example 2

Input: root = [5, 4, 6, null, null, 3, 7]
Output: false

Why: Every parent–child pair looks fine, but 3 sits in the right subtree of 5 and is smaller than 5.

Example 3

Input: root = [1, 1]
Output: false

Why: Duplicates are not allowed — “strictly” less.

Constraints

1 ≤ number of nodes ≤ 10⁴
−2³¹ ≤ node value ≤ 2³¹ − 1

In the interview

How to answer it out loud

What it tests: Tree traversal, understanding the full BST rule, and handling integer edge cases.

1
Clarify
Clarify whether duplicates are allowed and the range of node values.
2
Implement
Traverse in order (or pass low/high bounds down the tree) and confirm the values are strictly increasing.
3
Verify
Test a grandparent violation, duplicates, and a node holding the smallest integer; explain O(n) time and O(h) space.

Approaches

From brute force to the best solution

Approach	Idea	Time	Space
Compare each node with its subtrees	For every node, find the max of its left subtree and the min of its right subtree.	O(n²) worst case	O(h)
DFS with (low, high) bounds	Pass down the range each node must fall inside.	O(n)	O(h)
Iterative in-order traversalBest	A BST read in order is strictly increasing; compare each value with the previous one.	O(n)	O(h)

Key insight

Checking only a node against its children misses the second example. In-order traversal checks every ancestor constraint at once, and a “has previous” flag avoids the INT_MIN sentinel bug when the tree contains the smallest integer.

Solution

Reference solution

Each version is self-contained and has been run against the examples and test cases on this page.

1from typing import Optional234class TreeNode:5    def __init__(self, val=0, left=None, right=None):6        self.val, self.left, self.right = val, left, right789def is_valid_bst(root: Optional[TreeNode]) -> bool:10    # In-order traversal of a BST visits values in strictly increasing order.11    stack, prev, node = [], None, root12    while stack or node:13        while node:                 # walk left as far as possible14            stack.append(node)15            node = node.left16        node = stack.pop()17        if prev is not None and node.val <= prev:18            return False19        prev = node.val20        node = node.right21    return True

Time: O(n)
Space: O(h)
Approach: Iterative in-order traversal

Test cases

Edge cases to run before you say “done”

Input	Expected	Why it matters
[5, 4, 6, null, null, 3, 7]	false	The grandparent rule.
[-2147483648]	true	Breaks solutions that start from an INT_MIN sentinel.
[2, 2, 2]	false	Equal values are invalid.

Likely follow-ups

Answer the main question first, then take these on one at a time:

Can you solve it recursively with bounds?
How would you find two swapped nodes in an almost-valid BST?
What if the tree is too deep for recursion?

Avoid these mistakes

Check your recording or written solution against this list:

Comparing a node only with its direct children
Using INT_MIN or INT_MAX as a sentinel
Allowing equal values without asking

Sources and methodology

This guide combines general interview-practice patterns with the public hiring material below. The practice prompt and coaching are PiriPiri AI editorial content, not official Microsoft questions or answers.

Microsoft Careers: technical interviewing ↗

Official sources reviewed 20 September 2026.