18  Validate a Binary Search Tree

Rank 16 · Pattern: recursive traversal carrying valid bounds · Target: \(O(n)\) time, \(O(h)\) space

18.1 Problem definition

Given the root of a binary tree, return whether it is a valid binary search tree: every node’s entire left subtree must contain smaller values, and its entire right subtree must contain larger values.

18.2 Clarifying questions

  1. Are duplicate values valid, and if so, on which side?
  2. Should an empty tree be considered a valid binary search tree?
  3. What value range can nodes contain?
  4. Can I assume the input is a valid tree structure with no cycles or shared child nodes?

18.3 Sample answers

  1. Duplicates are invalid; both comparisons are strict.
  2. Yes. An empty tree is valid.
  3. A node may contain any signed 32-bit int, including Integer.MIN_VALUE and Integer.MAX_VALUE.
  4. Yes. Only the binary-search ordering needs validation.

18.4 Special data structure: TreeNode

The node has value, left, and right fields or owned links as in Chapter 17. A valid tree may be skewed, so its height \(h\) can range from \(O(\log n)\) when balanced to \(O(n)\).

       5
      / \
     1   7
        /
       4   <- locally 4 < 7, but globally invalid: 4 is right of 5

18.5 Approach and invariant

Carry an exclusive (low, high) range down the recursion:

  • root: (-∞, +∞);
  • left child: (low, node.value);
  • right child: (node.value, high).

Use long bounds so Integer.MIN_VALUE and Integer.MAX_VALUE remain strictly inside the initial range.

Use positive and negative infinity as initial bounds. Python integers are unbounded, and comparisons with these infinities express the open root range directly.

Store i32 node values and carry i64 bounds. Converting each value with i64::from avoids boundary arithmetic and overflow.

Using node-width bounds with value - 1 or value + 1 risks overflow.

Invariant: valid(node, low, high) returns true exactly when every node in that subtree obeys all ancestor constraints represented by low < value < high.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["Call valid(node, low, high)"]
  B{"Is node null?"}
  C["YES: return true"]
  D{"NO: is low less than value and value less than high?"}
  E["NO: return false"]
  F["YES: validate left with high = value"]
  G["Validate right with low = value"]
  H["Return true only if both subtrees are valid"]

  A --> B
  B --> C
  B --> D
  D --> E
  D --> F
  F --> G
  G --> H

  classDef plain fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,C,D,E,F,G,H plain;

18.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class ValidateBstSolution {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode(int value) { this.value = value; }
    }

    static boolean isValidBst(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    static boolean valid(TreeNode node, long low, long high) {
        if (node == null) {
            return true;
        }
        if (node.value <= low || node.value >= high) {
            return false;
        }
        return valid(node.left, low, node.value)
            && valid(node.right, node.value, high);
    }

    @Test public void acceptsEmptyTree() {
        assertTrue(isValidBst(null));
    }

    @Test public void acceptsSingleNode() {
        assertTrue(isValidBst(new TreeNode(2)));
    }

    @Test public void acceptsOrdinaryValidTree() {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        assertTrue(isValidBst(root));
    }

    @Test public void rejectsImmediateOrderingViolation() {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(3);
        assertFalse(isValidBst(root));
    }

    @Test public void rejectsDeepViolation() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(1);
        root.right = new TreeNode(7);
        root.right.left = new TreeNode(4);
        assertFalse(isValidBst(root));
    }

    @Test public void rejectsDeepViolationInLeftSubtree() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(6);
        assertFalse(isValidBst(root));
    }

    @Test public void rejectsDuplicatesOnEitherSide() {
        TreeNode leftDuplicate = new TreeNode(2);
        leftDuplicate.left = new TreeNode(2);
        assertFalse(isValidBst(leftDuplicate));

        TreeNode rightDuplicate = new TreeNode(2);
        rightDuplicate.right = new TreeNode(2);
        assertFalse(isValidBst(rightDuplicate));
    }

    @Test public void acceptsIntegerExtremes() {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(Integer.MIN_VALUE);
        root.right = new TreeNode(Integer.MAX_VALUE);
        assertTrue(isValidBst(root));
    }

    public static void main(String[] args) {
        JUnitCore.main("ValidateBstSolution");
    }
}
import unittest


class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def is_valid_bst(root):
    def valid(node, low, high):
        if node is None:
            return True
        if node.value <= low or node.value >= high:
            return False
        return valid(node.left, low, node.value) and valid(
            node.right, node.value, high
        )

    return valid(root, float("-inf"), float("inf"))


class ValidateBstTests(unittest.TestCase):
    def test_accepts_empty_tree(self):
        self.assertTrue(is_valid_bst(None))

    def test_accepts_ordinary_valid_tree(self):
        root = TreeNode(2, TreeNode(1), TreeNode(3))
        self.assertTrue(is_valid_bst(root))

    def test_rejects_immediate_violation(self):
        root = TreeNode(2, TreeNode(3))
        self.assertFalse(is_valid_bst(root))

    def test_rejects_deep_violation(self):
        root = TreeNode(5, TreeNode(1), TreeNode(7, TreeNode(4)))
        self.assertFalse(is_valid_bst(root))

    def test_rejects_duplicates(self):
        self.assertFalse(is_valid_bst(TreeNode(2, TreeNode(2))))
        self.assertFalse(is_valid_bst(TreeNode(2, right=TreeNode(2))))

    def test_accepts_large_integer_values(self):
        root = TreeNode(0, TreeNode(-(10**100)), TreeNode(10**100))
        self.assertTrue(is_valid_bst(root))


if __name__ == "__main__":
    unittest.main()
#[derive(Debug)]
pub struct TreeNode {
    pub value: i32,
    pub left: Link,
    pub right: Link,
}

pub type Link = Option<Box<TreeNode>>;

impl TreeNode {
    pub fn new(value: i32) -> Self {
        Self {
            value,
            left: None,
            right: None,
        }
    }
}

pub fn is_valid_bst(root: &Link) -> bool {
    fn valid(node: &Link, low: i64, high: i64) -> bool {
        let Some(node) = node else {
            return true;
        };
        let value = i64::from(node.value);
        if value <= low || value >= high {
            return false;
        }
        valid(&node.left, low, value) && valid(&node.right, value, high)
    }

    valid(root, i64::MIN, i64::MAX)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn node(value: i32) -> Box<TreeNode> {
        Box::new(TreeNode::new(value))
    }

    #[test]
    fn accepts_empty_tree() {
        assert!(is_valid_bst(&None));
    }

    #[test]
    fn accepts_ordinary_valid_tree() {
        let mut root = node(2);
        root.left = Some(node(1));
        root.right = Some(node(3));
        assert!(is_valid_bst(&Some(root)));
    }

    #[test]
    fn rejects_immediate_violation() {
        let mut root = node(2);
        root.left = Some(node(3));
        assert!(!is_valid_bst(&Some(root)));
    }

    #[test]
    fn rejects_deep_violation() {
        let mut root = node(5);
        root.left = Some(node(1));
        let mut right = node(7);
        right.left = Some(node(4));
        root.right = Some(right);
        assert!(!is_valid_bst(&Some(root)));
    }

    #[test]
    fn rejects_duplicates() {
        let mut root = node(2);
        root.left = Some(node(2));
        assert!(!is_valid_bst(&Some(root)));
    }

    #[test]
    fn accepts_integer_extremes() {
        let mut root = node(0);
        root.left = Some(node(i32::MIN));
        root.right = Some(node(i32::MAX));
        assert!(is_valid_bst(&Some(root)));
    }
}

18.7 High-value tests

Tree Expected Purpose
empty true conventional empty BST
one node true base case
2 with children 1,3 true ordinary valid
deep violation shown above false ancestor constraint
duplicate child false strictness
node Integer.MIN_VALUE true bound width

18.8 Complexity and correctness

Each node is checked once: \(O(n)\) time. Recursive space is \(O(h)\), worst-case \(O(n)\) for a skewed tree.

The root has no finite constraint. At each recursive step, the node is checked against all inherited ancestor constraints, and its value tightens the appropriate boundary for descendants. If both subtrees meet those exact ranges, every left descendant is smaller and every right descendant larger; the converse follows because any invalid descendant fails one inherited bound.

18.9 If the interviewer pushes

  • An in-order traversal of a valid strict BST is strictly increasing. Track the previous node carefully, including integer extremes.
  • Use an explicit stack to avoid recursion overflow on a deeply skewed tree.
  • If duplicates are allowed on one side, adjust one boundary to be inclusive and document the policy.
  • Validation does not prove that the structure is acyclic; tree inputs conventionally guarantee this.

18.10 TDD interview script

Confirm that duplicates are invalid, an empty tree is valid, node values may be any int, and the structure itself is a valid tree. Then write this test list:

  1. Empty tree
  2. Singleton
  3. Ordinary valid tree
  4. Immediate violation
  5. Deep violations on both sides
  6. Duplicates on either side
  7. Integer extremes

Add one focused test per red–green–refactor cycle. Build small trees whose violated rule is visually obvious, confirm red, change only the recursive range logic required, and rerun the complete example. Test through the public validation function; do not assert private recursion order.

From book/src, run:

./java/run.sh ValidateBstSolution
./python/run.sh validate_bst_solution
./rust/run.sh validate_bst_solution

Use the deep violation to explain why parent-child comparisons are insufficient: every recursive call must carry all ancestor restrictions compressed into one exclusive lower and upper bound.

18.10.1 Pseudocode

isValidBst(root):
    return valid(root, negative infinity, positive infinity)

valid(node, low, high):
    if node is null:
        return true
    if node.value <= low or node.value >= high:
        return false
    return valid(node.left, low, node.value)
       and valid(node.right, node.value, high)

The invariant is: valid(node, low, high) is true exactly when every node in that subtree satisfies all ancestor constraints represented by low < value < high.

18.10.2 TDD sequence

Step Test code added Production code added or changed
1. Empty subtree acceptsEmptyTree Make null the recursive true base case.
2. Root in range acceptsSingleNode Introduce exclusive low/high bounds and accept a node strictly between them.
3. Tighten child bounds acceptsOrdinaryValidTree Recurse left with high = node.value and right with low = node.value.
4. Local violation rejectsImmediateOrderingViolation Return false when a value reaches or crosses either bound.
5. Right-subtree ancestor rule rejectsDeepViolation Carry the root’s lower bound into descendants of its right child.
6. Left-subtree ancestor rule rejectsDeepViolationInLeftSubtree Symmetrically carry the root’s upper bound through the left subtree.
7. Strict ordering rejectsDuplicatesOnEitherSide Keep both boundary comparisons exclusive using <= and >=.
8. Full integer domain acceptsIntegerExtremes Use long sentinel bounds rather than int bounds or value-plus/minus-one arithmetic.

This progression first establishes recursive structure, then triangulates inherited constraints from both directions. Extreme-value testing guards the representation of infinity, not just the tree logic.