Validate a binary search tree
Determine whether every node in a binary tree satisfies strict binary-search-tree ordering with no duplicate values.
Course progress
Problem 84 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
root 5; left 1; right 4 with children 3 and 6
Expected output
False
What is happening?
Every value in the right subtree of 5 must exceed 5, but its root is 4. That bound violation makes the tree invalid.
Solution strategy
Build the right mental model
Pass an allowed lower and upper bound down the tree. Each node narrows the range for its children.
Core concepts
binary tree · recursion
Complexity
Time O(n), call-stack space O(h).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for validate-binary-search-tree
using System;
class Program
{
class Node
{
public int Value { get; private set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int value) { Value = value; }
}
static bool IsValid(Node node, long lower, long upper)
{
if (node == null) return true;
if (node.Value <= lower || node.Value >= upper) return false;
return IsValid(node.Left, lower, node.Value) &&
IsValid(node.Right, node.Value, upper);
}
static void Main()
{
Node root = new Node(5) {
Left = new Node(1),
Right = new Node(4) { Left = new Node(3), Right = new Node(6) }
};
Console.WriteLine(IsValid(root, long.MinValue, long.MaxValue));
}
}Knowledge check
Questions students often ask
What is the main idea behind validate a binary search tree?
Pass an allowed lower and upper bound down the tree. Each node narrows the range for its children.
What is the time and space complexity of this solution?
Time O(n), call-stack space O(h).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.