Validate Binary Search Tree solution and explanation
IBM
Google
9 more videos on this problem
Validate Binary Search Tree - Depth First Search - Leetcode 98NeetCode · 9:56 · 327K views
LeetCode 98. Validate Binary Search Tree (Algorithm Explained)Nick White · 9:48 · 53K views
Validate Binary Search Tree (LeetCode 98) | Full solution with animations and visualsNikhil Lohia · 16:35 · 15K views
Validate Binary Search Tree - Leetcode 98 - Trees (Python)Greg Hogg · 8:12 · 13K views
LeetCode 98. Validate Binary Search Tree - Interview Prep Ep 69Fisher Coder · 9:56 · 7K views
Validate Binary Search Tree - LeetCode 98 - JavaScriptAlgoJS · 5:58 · 3K views
Validate Binary Search Tree - LeetCode 98 - PythonDeepti Talesra · 17:28 · 3K views
[Java] Leetcode 98. Validate Binary Search Tree [Binary Search Tree #3]Eric Programming · 11:11 · 3K views
Validate Binary Search Tree - LeetCode 98 - Coding Interview QuestionsOne Code Man · 3:49 · 2K views
Validate Binary Search Tree | Leetcode 98Knowledge Center · 19:35 · 1K views
The problem
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
Approach overview
Problem Overview: You’re given the root of a binary tree and need to verify whether it satisfies the rules of a Binary Search Tree (BST). Every node must follow the constraint left subtree < node < right subtree, and this rule must hold for every node in the tree.
Approach 1: Recursive In-Order Traversal (O(n) time, O(h) space)
A key property of a valid BST is that an in-order traversal visits nodes in strictly increasing order. Traverse the tree using recursion: visit the left subtree, process the current node, then visit the right subtree. While traversing, track the value of the previously visited node. If the current node’s value is less than or equal to the previous value, the BST property is violated and the tree is invalid.
This approach works because binary search trees naturally produce sorted output during in-order traversal. The recursion depth depends on the tree height, so the space complexity is O(h), where h is the height of the tree. In balanced trees this is O(log n), but it becomes O(n) in the worst case of a skewed tree. The time complexity remains O(n) because each node is visited exactly once.
Approach 2: Iterative In-Order Traversal (O(n) time, O(h) space)
This version performs the same in-order traversal but replaces recursion with an explicit stack. Start at the root and repeatedly push nodes while moving left until you reach a null node. Pop from the stack, process the node, then move to its right child. During each visit, compare the current value with the previously visited value to ensure the sequence remains strictly increasing.
The iterative approach avoids recursion and gives you more control over the traversal process. It uses a stack to simulate the call stack typically used in depth-first search. Time complexity is still O(n) since every node is pushed and popped once. Space complexity remains O(h) due to the stack storing nodes along the current path from the root to a leaf.
Both approaches rely on the structural property of tree traversal rather than explicitly checking value ranges for every subtree. The sorted in-order sequence provides a simple and reliable validation mechanism.
Recommended for interviews: Recursive in-order traversal is the most common solution interviewers expect because it clearly demonstrates understanding of BST properties and DFS traversal. The iterative version is equally efficient and shows stronger control over stack-based traversal, which can stand out in more advanced interviews.
Approach 1: Approach 1: Recursive In-Order Traversal
This approach involves recursively traversing the binary tree in an in-order manner, comparing each node's value with a running minimum and maximum valid value, to ensure the BST properties hold. The initial minimum and maximum allow for any integer value, and they get updated as we traverse the tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def validate(node, low=-float('inf'), high=float('inf')):
if not node:
return True
if not (low < node.val < high):
return False
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool validate(TreeNode* node, long min, long max) {
if (!node) return true;
if (node->val <= min || node->val >= max) return false;
return validate(node->left, min, node->val) &&
validate(node->right, node->val, max);
}
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}
};function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var isValidBST = function(root) {
const validate = (node, min, max) => {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
};
return validate(root, -Infinity, Infinity);
};#include <limits.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool validate(struct TreeNode* node, long min, long max) {
if (node == NULL) return true;
if (node->val <= min || node->val >= max) return false;
return validate(node->left, min, node->val) &&
validate(node->right, node->val, max);
}
bool isValidBST(struct TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsValidBST(TreeNode root) {
return Validate(root, long.MinValue, long.MaxValue);
}
private bool Validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return Validate(node.left, min, node.val) && Validate(node.right, node.val, max);
}
}The function validate checks the validity of the current node and recursively validates its subtrees by narrowing the valid range for node values.
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(h) due to recursive calls.
Approach 2: Approach 2: Iterative In-Order Traversal
This approach involves an iterative in-order traversal using a stack to ensure non-decreasing order of node values. We iterate through the nodes using the stack and at each step, compare the current node's value with the last visited node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack = []
current = root
prevVal = -float('inf')
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
if current.val <= prevVal:
return False
prevVal = current.val
current = current.right
return Trueimport java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
long prevVal = Long.MIN_VALUE;
while (!stack.isEmpty() || current != null) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (current.val <= prevVal)
return false;
prevVal = current.val;
current = current.right;
}
return true;
}
}#include <stack>
#include <limits.h>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isValidBST(TreeNode* root) {
std::stack<TreeNode*> stack;
TreeNode* current = root;
long prevVal = LONG_MIN;
while (!stack.empty() || current != nullptr) {
while (current != nullptr) {
stack.push(current);
current = current->left;
}
current = stack.top(); stack.pop();
if (current->val <= prevVal)
return false;
prevVal = current->val;
current = current->right;
}
return true;
}
};function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var isValidBST = function(root) {
const stack = [];
let current = root;
let prevVal = -Infinity;
while (stack.length > 0 || current !== null) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (current.val <= prevVal) return false;
prevVal = current.val;
current = current.right;
}
return true;
};#include <stdbool.h>
#include <stdlib.h>
#include <limits.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct Stack {
struct TreeNode **data;
int top;
};
void push(struct Stack *stack, struct TreeNode *node) {
stack->data[++stack->top] = node;
}
struct TreeNode *pop(struct Stack *stack) {
return stack->data[stack->top--];
}
bool isEmpty(struct Stack *stack) {
return stack->top == -1;
}
bool isValidBST(struct TreeNode* root) {
struct Stack stack = { .data = malloc(10000 * sizeof(struct TreeNode *)), .top = -1 };
struct TreeNode *current = root;
long prevVal = LONG_MIN;
while (!isEmpty(&stack) || current != NULL) {
while (current != NULL) {
push(&stack, current);
current = current->left;
}
current = pop(&stack);
if (current->val <= prevVal)
return false;
prevVal = current->val;
current = current->right;
}
free(stack.data);
return true;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool IsValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
long prevVal = long.MinValue;
while (stack.Count > 0 || current != null) {
while (current != null) {
stack.Push(current);
current = current.left;
}
current = stack.Pop();
if (current.val <= prevVal) return false;
prevVal = current.val;
current = current.right;
}
return true;
}
}This Python solution uses a list as a stack to conduct iterative in-order traversal. It checks each node's value against the last visited to determine BST validity.
Time Complexity: O(n), with a single traversal of tree.
Space Complexity: O(h) for the stack, dependent on height.
Approach 3: Recursion
We can perform a recursive in-order traversal on the binary tree. If the result of the traversal is strictly ascending, then this tree is a binary search tree.
Therefore, we use a variable prev to save the last node we traversed. Initially, prev = -∞. Then we recursively traverse the left subtree. If the left subtree is not a binary search tree, we directly return False. Otherwise, we check whether the value of the current node is greater than prev. If not, we return False. Otherwise, we update prev to the value of the current node, and then recursively traverse the right subtree.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isValidBST(root: TreeNode | null): boolean {
let prev: TreeNode | null = null;
const dfs = (root: TreeNode | null): boolean => {
if (!root) {
return true;
}
if (!dfs(root.left)) {
return false;
}
if (prev && prev.val >= root.val) {
return false;
}
prev = root;
return dfs(root.right);
};
return dfs(root);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
var prev *TreeNode
var dfs func(*TreeNode) bool
dfs = func(root *TreeNode) bool {
if root == nil {
return true
}
if !dfs(root.Left) {
return false
}
if prev != nil && prev.Val >= root.Val {
return false
}
prev = root
return dfs(root.Right)
}
return dfs(root)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, prev: &mut Option<i32>) -> bool {
if root.is_none() {
return true;
}
let root = root.as_ref().unwrap().borrow();
if !Self::dfs(&root.left, prev) {
return false;
}
if prev.is_some() && prev.unwrap() >= root.val {
return false;
}
*prev = Some(root.val);
Self::dfs(&root.right, prev)
}
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
Self::dfs(&root, &mut None)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Recursive In-Order Traversal | Time Complexity: O(n) since each node is visited once. |
| Approach 2: Iterative In-Order Traversal | Time Complexity: O(n), with a single traversal of tree. |
| Recursion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive In-Order Traversal | O(n) | O(h) | Standard interview solution. Clean and easy to implement when recursion is acceptable. |
| Iterative In-Order Traversal | O(n) | O(h) | Useful when avoiding recursion or demonstrating explicit stack-based DFS traversal. |
Frequently asked questions
Is Validate Binary Search Tree easy or hard?
Validate Binary Search Tree is considered a Medium difficulty problem on LeetCode. The challenge comes from correctly applying BST properties across the entire subtree rather than only comparing immediate parent and child nodes.
Validate Binary Search Tree Python/Java solution
In Python or Java, the standard solution performs an in-order traversal and tracks the previous node value. If the current node value is less than or equal to the previous value, return false. Otherwise continue traversal until all nodes are processed.
How to solve Validate Binary Search Tree in O(n)?
Perform an in-order traversal and maintain a variable storing the previously visited node value. For each node, check that the current value is strictly greater than the previous one. If the order ever breaks, the tree is not a valid BST. This ensures O(n) time since every node is processed once.
What is the best approach for Validate Binary Search Tree?
The most common approach uses in-order traversal of the tree. A valid binary search tree produces a strictly increasing sequence when traversed in-order. By tracking the previously visited value and ensuring each new value is greater, you can validate the BST in O(n) time with O(h) space.
Is Validate Binary Search Tree asked at Google/Amazon/Meta?
Validate Binary Search Tree is a common interview question at major tech companies including Google, Amazon, and Meta. It tests understanding of tree traversal, recursion, and the core properties of binary search trees.
What data structure is used in Validate Binary Search Tree?
The problem uses a binary tree structure and typically relies on depth-first search traversal. Implementations use recursion or an explicit stack to perform in-order traversal while checking BST ordering constraints.
What is the time complexity of Validate Binary Search Tree?
The optimal solution runs in O(n) time because each node in the tree is visited exactly once during traversal. Space complexity is O(h), where h is the height of the tree, due to recursion stack or an explicit stack used in iterative traversal.