Start learning free

LESSON 411 OF 539 · BINARY TREES

Validate Binary Search Tree in C#: Recursion with Bounds in O(n)

Practice O(n) Read the full explanation

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

A binary tree is a valid BST when, for every node:

every value in its left subtree is strictly smaller than the node's value,
every value in its right subtree is strictly larger than the node's value.

The rule is about the whole subtree, not only the children: a node's value must also fit every node above it.

The trees below are written in level order (top to bottom, left to right), with null for a missing child.

Example 1:

     2
    / \
   1   3

Input: root = [2,1,3]
Output: true
Explanation: 1 is smaller than 2 and 3 is larger.

Example 2:

     5
    / \
   1   4
      / \
     3   6

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The right child of the root 5 is 4, which is smaller than 5.

Example 3:

     5
    / \
   4   6
      / \
     3   7

Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: Every node is in order with its own children: 4 < 5 < 6 and 3 < 6 < 7. But 3 is in the right subtree of 5, where every value must be larger than 5. Comparing each node only with its children misses this: each node must lie in the range that all of its ancestors set.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
Each node value is between -2³¹ and 2³¹ - 1.
The tree is at most 800 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, visiting each node once.

Node values can be the smallest and the largest 32-bit integers, so a bound that means "no limit yet" can't be one of those values.

STEP 1 OF 5

Guided

Ctrl + Enter to check

C# · BINARY TREES

Validate Binary Search Tree in C#, explained

Problem overview

The method IsValidBST receives root, the root of a binary tree, and returns true when the tree is a valid binary search tree. For every node, every value in its left subtree must be strictly smaller than the node's value, and every value in its right subtree must be strictly larger. The rule covers the whole subtree, not only the two children. The lesson provides the TreeNode class with the fields val, left and right.

[2, 1, 3] is valid: 1 is smaller than 2 and 3 is larger.
[5, 1, 4, null, null, 3, 6] is not valid: the right child of 5 is 4, which is smaller than 5.
[5, 4, 6, null, null, 3, 7] is not valid, although every node is in order with its own children (4 < 5 < 6 and 3 < 6 < 7). The 3 lies in the right subtree of 5, where every value must be larger than 5.

Approach: pass the allowed range down

The third example is the trap. Comparing each node only with its children accepts that tree, because the mistake is between a node and a grandchild. The fix is to remember what the ancestors demand. Each node must lie strictly inside a range (low, high) that comes from the nodes above it:

The root can hold any value, so its range is unlimited.
Going into a left child, the node's value becomes the new upper bound: everything on the left must be smaller.
Going into a right child, the node's value becomes the new lower bound: everything on the right must be larger.
The other bound is inherited unchanged, which is how the demands of higher ancestors stay in force.

In the third example, the 3 is reached through the 5's right side, so its range is (5, 6), and the 3 fails it.

The bounds start as "no limit yet". Node values can be as small as -2147483648 and as large as 2147483647, the smallest and largest int. If the unlimited bounds were int.MinValue and int.MaxValue, a node holding one of those values would equal a bound, fail the strict test, and a perfectly valid tree would be rejected. The bounds are therefore long, which holds every int with room to spare.

Each node is visited once, so the time is O(n).

Step by step

Start in IsValidBST. Call the helper Validate on root with long.MinValue and long.MaxValue as the bounds, and return its answer. The root has no ancestors, so nothing limits it yet.
Declare Validate as a public bool method taking a TreeNode node and two long values, low and high. It returns true when every value under node is larger than low and smaller than high.
Handle the empty tree. If node == null, return true: an empty subtree breaks no rule, and this check also ends the recursion past a leaf.
Check the node's own value. If node.val <= low || node.val >= high, return false. The test is strict, so a value equal to a bound is also rejected. An int compared with a long works directly because C# widens the int.
Check both subtrees. The left subtree gets (low, node.val) and the right subtree gets (node.val, high). Join the two recursive calls with &&.

The solution in C#

class Solution {
    public bool Validate(TreeNode node, long low, long high) {
        if (node == null) {
            return true;
        }
        if (node.val <= low || node.val >= high) {
            return false;
        }
        return Validate(node.left, low, node.val) && Validate(node.right, node.val, high);
    }
    public bool IsValidBST(TreeNode root) {
        return Validate(root, long.MinValue, long.MaxValue);
    }
}

The C# details worth knowing:

Implicit widening. Passing node.val, an int, where a long parameter is expected needs no cast. Widening to a larger type never loses information, so C# does it automatically. The reverse, long to int, needs an explicit cast.
long.MinValue and long.MaxValue. These are the constants of the 64-bit type, -9223372036854775808 and 9223372036854775807. Every int is strictly between them.
Short-circuit &&. When the left subtree is already invalid, the right call isn't made. The answer is false either way.
Null checks. node == null is how C# tests for a missing child. Reading node.val on a null node would throw a NullReferenceException, which is why the null test comes first.

Complexity

Time: O(n). Each node is checked once, with a constant amount of work, and the recursion visits each missing child once as well.

Space: O(h), where h is the height of the tree, for the call stack. The statement allows up to 800 levels, which the default stack handles. A chain of n nodes would use O(n) stack.

Edge cases and common mistakes

Comparing only with the children. This accepts [5, 4, 6, null, null, 3, 7], which is invalid. In a run, the child-only check returns true for that tree, while the bounds version returns false.
Using int bounds. A single node holding 2147483647 is a valid tree, but a version with int.MinValue and int.MaxValue as the starting bounds returns false for it, because the value equals the upper bound.
Duplicates. The rule is strict, so [2, 2, 2] is not valid. Using < where the code uses <= would accept it.
A single node. Any single node is valid, including one holding int.MinValue or int.MaxValue.
Negative values. [0, -1] is valid. The bounds handle negatives like any other numbers.
Swapping the bounds. The left child must get the node's value as its upper bound, and the right child as its lower bound.

Testing

[2, 1, 3] gives true.
[5, 1, 4, null, null, 3, 6] gives false.
[5, 4, 6, null, null, 3, 7] gives false.
[2, 2, 2] gives false.
[2147483647] gives true.
[-2147483648, null, 2147483647] gives true.
[0, -1] gives true.

Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free