Validate Binary Search Tree

Problem Statement

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

A valid BST is defined as:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree contains only nodes with keys greater than the node’s key.
• Both left and right subtrees must also be binary search trees.

Examples

Input	Output	Explanation
[2,1,3]	true	1 < 2 < 3 ✓
[5,1,4,null,null,3,6]	false	Node 4 should be > 5

Constraints

• The number of nodes is in range [1, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space
DFS with Bounds	O(n)	O(h)
In-Order Traversal	O(n)	O(h)

Approach 1: DFS with Min/Max Bounds (Recommended)

★ Recommended

Track min and max bounds as you traverse. Left child must be > min, right child must be < max.

⏱ Time O(n) 💾 Space O(h)

Solution Code

Python

validate_binary_search_tree_bounds.py

from typing import Optional

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

def isValidBST(root: Optional[TreeNode]) -> bool:
    def dfs(node: Optional[TreeNode], min_val: float, max_val: float) -> bool:
        if not node: return True
        if not (min_val < node.val < max_val): return False
        return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)
    return dfs(root, float('-inf'), float('inf'))

if __name__ == "__main__":
    root = TreeNode(2)
    root.left, root.right = TreeNode(1), TreeNode(3)
    print(isValidBST(root))  # True

C++

validate_binary_search_tree_bounds.cpp

#include <iostream>
#include <climits>
using namespace std;

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

bool dfs(TreeNode* n, long long minVal, long long maxVal) {
    if (!n) return true;
    if (n->val <= minVal || n->val >= maxVal) return false;
    return dfs(n->left, minVal, n->val) && dfs(n->right, n->val, maxVal);
}

bool isValidBST(TreeNode* root) {
    return dfs(root, LLONG_MIN, LLONG_MAX);
}

Java

validate_binary_search_tree_bounds.java

public class Solution {
    boolean dfs(TreeNode n, long minVal, long maxVal) {
        if (n == null) return true;
        if (n.val <= minVal || n.val >= maxVal) return false;
        return dfs(n.left, minVal, n.val) && dfs(n.right, n.val, maxVal);
    }
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
}

JavaScript

validate_binary_search_tree_bounds.js

function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

function isValidBST(root) {
    function dfs(n, minVal, maxVal) {
        if (!n) return true;
        if (n.val <= minVal || n.val >= maxVal) return false;
        return dfs(n.left, minVal, n.val) && dfs(n.right, n.val, maxVal);
    }
    return dfs(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
}
module.exports = isValidBST;

Rust

validate_binary_search_tree_bounds.rs

use std::cell::RefCell; use std::rc::Rc;
#[derive(Debug)]
pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, }
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, min: i64, max: i64) -> bool {
        if let Some(node) = n {
            let node_ref = node.borrow();
            if (node_ref.val as i64) <= min || (node_ref.val as i64) >= max { return false; }
            dfs(&node_ref.left, min, node_ref.val as i64) && dfs(&node_ref.right, node_ref.val as i64, max)
        } else { true }
    }
    dfs(&root, i64::MIN, i64::MAX)
}

Go

validate_binary_search_tree_bounds.go

package main

import "math"

type TreeNode struct { Val int; Left, Right *TreeNode }

func IsValidBST(root *TreeNode) bool {
    var dfs func(*TreeNode, float64, float64) bool
    dfs = func(n *TreeNode, minVal, maxVal float64) bool {
        if n == nil { return true }
        if float64(n.Val) <= minVal || float64(n.Val) >= maxVal { return false }
        return dfs(n.Left, minVal, float64(n.Val)) && dfs(n.Right, float64(n.Val), maxVal)
    }
    return dfs(root, math.Inf(-1), math.Inf(1))
}

Approach 2: In-Order Traversal

🎯 Interview Favourite

In-order traversal of a valid BST yields sorted values. Track previous value and ensure it’s always increasing.

⏱ Time O(n) 💾 Space O(h)

Solution Code

Python

validate_binary_search_tree_inorder.py

from typing import Optional

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

def isValidBST(root: Optional[TreeNode]) -> bool:
    prev = [float('-inf')]
    def dfs(node: Optional[TreeNode]) -> bool:
        if not node: return True
        if not dfs(node.left): return False
        if node.val <= prev[0]: return False
        prev[0] = node.val
        return dfs(node.right)
    return dfs(root)

if __name__ == "__main__":
    root = TreeNode(2)
    root.left, root.right = TreeNode(1), TreeNode(3)
    print(isValidBST(root))  # True

C++

validate_binary_search_tree_inorder.cpp

#include <iostream>
#include <climits>
using namespace std;

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

bool isValidBST(TreeNode* root) {
    long long prev = LLONG_MIN;
    function<bool(TreeNode*)> dfs = [&](TreeNode* n) -> bool {
        if (!n) return true;
        if (!dfs(n->left)) return false;
        if (n->val <= prev) return false;
        prev = n->val;
        return dfs(n->right);
    };
    return dfs(root);
}

Java

validate_binary_search_tree_inorder.java

public class Solution {
    long[] prev = {Long.MIN_VALUE};
    boolean dfs(TreeNode n) {
        if (n == null) return true;
        if (!dfs(n.left)) return false;
        if (n.val <= prev[0]) return false;
        prev[0] = n.val;
        return dfs(n.right);
    }
    public boolean isValidBST(TreeNode root) {
        return dfs(root);
    }
    public static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
}

JavaScript

validate_binary_search_tree_inorder.js

function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

function isValidBST(root) {
    let prev = Number.NEGATIVE_INFINITY;
    function dfs(n) {
        if (!n) return true;
        if (!dfs(n.left)) return false;
        if (n.val <= prev) return false;
        prev = n.val;
        return dfs(n.right);
    }
    return dfs(root);
}
module.exports = isValidBST;

Rust

validate_binary_search_tree_inorder.rs

use std::cell::RefCell; use std::rc::Rc;
#[derive(Debug)]
pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, }
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    let prev = std::cell::RefCell::new(i64::MIN);
    fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, prev: &std::cell::RefCell<i64>) -> bool {
        if let Some(node) = n {
            let node_ref = node.borrow();
            if !dfs(&node_ref.left, prev) { return false; }
            let mut p = prev.borrow_mut();
            if (node_ref.val as i64) <= *p { return false; }
            *p = node_ref.val as i64;
            dfs(&node_ref.right, prev)
        } else { true }
    }
    dfs(&root, &prev)
}

Go

validate_binary_search_tree_inorder.go

package main

import "math"

type TreeNode struct { Val int; Left, Right *TreeNode }

func IsValidBST(root *TreeNode) bool {
    prev := []float64{math.Inf(-1)}
    var dfs func(*TreeNode) bool
    dfs = func(n *TreeNode) bool {
        if n == nil { return true }
        if !dfs(n.Left) { return false }
        if float64(n.Val) <= prev[0] { return false }
        prev[0] = float64(n.Val)
        return dfs(n.Right)
    }
    return dfs(root)
}

Interview Tips

Key trade-offs to discuss

• Time vs. space trade-offs between approaches
• Handling edge cases (empty inputs, single elements, duplicates)
• Optimization opportunities and when they matter
• Follow-up variations and constraint changes