DSA-084 · Carry strict bounds inherited from all ancestors

Validate Binary Search Tree

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 23503 deterministic checks. Learner drafts are not executed.

Understand the problem

Return whether a proper binary tree is a strict binary search tree: every left descendant is smaller and every right descendant is larger than its ancestor.

Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
Preserve every original value, node identity, and left/right edge. Compact level-order arrays in examples are adapters, consuming two child slots per nonnull queued parent; they are not heap-indexed arrays.
Empty input is valid. Duplicate values are invalid anywhere. All int values, including MIN_VALUE and MAX_VALUE, are permitted when ordering allows them. Bounds use exclusive long endpoints outside the int domain; no value±1 arithmetic is needed.

Examples

Input: [2,1,3]
Output: true
Every descendant satisfies its inherited interval.
Input: [5,1,7,null,null,4,8]
Output: false
4 is less than its parent 7 but lies in root 5’s right subtree and must exceed 5.
Input: [MIN,null,MAX]
Output: true
Long exclusive bounds permit both int extremes.

Before you start

Global BST ordering versus parent-only comparisons
Exclusive bounds and integer-domain sentinels

Recognize the structure

A node’s legal range is the intersection of all ancestor decisions. Comparing only the immediate parent drops constraints. An inorder sequence is strictly increasing exactly when a proper binary tree is a strict BST.

Try before revealing

Hint 1

Can a grandparent impose a constraint the parent comparison misses?

Hint 2

Each node has an allowed open interval.

Hint 3

Pass (low,value) left and (value,high) right, with long outer sentinels.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Collect inorder values and check strict increase

Recursively emit left subtree, current value, right subtree into a list. Reject any adjacent nonincreasing pair. The invalid example emits 1,5,4,7,8, exposing 5≥4. This independent baseline is O(n) work but retains O(n) values and uses recursive calls.

Improve the baseline

Start with the whole int domain inside long bounds

Use (Long.MIN_VALUE,Long.MAX_VALUE), exclusive. All int values lie strictly inside it.

Validate before expanding

Pop (node,low,high). A value<=low or >=high violates an ancestor requirement and immediately returns false.

Intersect child ranges without arithmetic

Left inherits (low,node.value); right inherits (node.value,high). Passing the value itself with strict tests avoids overflow and enforces duplicate rejection.

Why it is correct

Range invariant

Each frame’s exclusive interval encodes exactly the constraints imposed by the root-to-node path.

Correct propagation

A left edge adds value<parent and a right edge adds value>parent. Intersecting with the previous interval preserves every ancestor’s condition.

Equivalence to the BST contract

Any violation is caught when its node is visited. If all frames pass, every node respects all its ancestors, exactly the strict global BST definition.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    private record Bound(Node node, long low, long high) {}
    public static boolean valid(Node root) {
        if (root == null) return true;
        ArrayDeque<Bound> stack = new ArrayDeque<>();
        stack.push(new Bound(root,Long.MIN_VALUE,Long.MAX_VALUE));
        while (!stack.isEmpty()) {
            Bound bound = stack.pop();
            Node node = bound.node;
            if (node.value <= bound.low || node.value >= bound.high) return false;
            if (node.right != null) stack.push(new Bound(node.right,node.value,bound.high));
            if (node.left != null) stack.push(new Bound(node.left,bound.low,node.value));
        }
        return true;
    }
    private static void inorder(Node node, List<Integer> values) {
        if (node == null) return;
        inorder(node.left,values); values.add(node.value); inorder(node.right,values);
    }
    public static boolean baseline(Node root) {
        List<Integer> values = new ArrayList<>(); inorder(root,values);
        for (int i = 1; i < values.size(); i++) if (values.get(i-1) >= values.get(i)) return false;
        return true;
    }
}

Read the meaningful blocks

Use long for boundary sentinels

An exclusive int MIN/MAX bound would incorrectly reject a legitimate extreme root.

Do not replace strict tests with ±1

Adding one to MAX or subtracting one from MIN can wrap; exclusive comparisons need no arithmetic.

Shape validity is a separate precondition

A range checker is not a cycle detector. The proper-tree contract supports one-visit traversal.

Complexity

Main method takes O(n) worst-case time and O(h) explicit bound frames, with possible early rejection. No sorted list or per-node map is retained.

The inorder baseline takes O(n) time and O(n+h) auxiliary storage, including its list and calls; recursion is limited to shallow validation inputs.

Exact-state walkthroughs

Reveal normal and boundary traces

Inherited exclusive intervals

Input: [2,1,3] · Result: true

Step 1 of 5: Use exclusive long bounds beyond the int domain.

null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.

BST validation — inherited exclusive intervals

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 2left → T1right → T2
T1: 1left → nullright → null
T2: 3left → nullright → null

Pending exclusive bounds — stack top at right

T0: (−∞, +∞)

Infinity labels represent Java long sentinels beyond the int domain. They are display labels, not imprecise JavaScript long numbers. Every ancestor constraint survives in the interval.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","low":null,"high":null}]`
checked	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Bound(Node node, long low, long high) {}
 9     public static boolean valid(Node root) {
10         if (root == null) return true;
11         ArrayDeque<Bound> stack = new ArrayDeque<>();
12         stack.push(new Bound(root,Long.MIN_VALUE,Long.MAX_VALUE));
13         while (!stack.isEmpty()) {
14             Bound bound = stack.pop();
15             Node node = bound.node;
16             if (node.value <= bound.low || node.value >= bound.high) return false;
17             if (node.right != null) stack.push(new Bound(node.right,node.value,bound.high));
18             if (node.left != null) stack.push(new Bound(node.left,bound.low,node.value));
19         }
20         return true;
21     }
22     private static void inorder(Node node, List<Integer> values) {
23         if (node == null) return;
24         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
25     }
26     public static boolean baseline(Node root) {
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         for (int i = 1; i < values.size(); i++) if (values.get(i-1) >= values.get(i)) return false;
29         return true;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Use exclusive long bounds beyond the int domain.
null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.
treeNodes
[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","low":null,"high":null}]
checked
[]
phase
"initial"
current
null
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T2","low":2,"high":null},{"id":"T1","low":null,"high":2}]
checked
[{"id":"T0","low":null,"high":null,"passes":true}]
phase
"accept"
current
"T0"
bound
{"id":"T0","low":null,"high":null}
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T2","low":2,"high":null}]
checked
[{"id":"T0","low":null,"high":null,"passes":true},{"id":"T1","low":null,"high":2,"passes":true}]
phase
"accept"
current
"T1"
bound
{"id":"T1","low":null,"high":2}
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
stack
[]
checked
[{"id":"T0","low":null,"high":null,"passes":true},{"id":"T1","low":null,"high":2,"passes":true},{"id":"T2","low":2,"high":null,"passes":true}]
phase
"accept"
current
"T2"
bound
{"id":"T2","low":2,"high":null}
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
true

A grandparent constraint rejects a descendant

Input: [5,1,7,null,null,4,8] · Result: false

Step 1 of 6: Use exclusive long bounds beyond the int domain.

null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.

BST validation — inherited exclusive intervals

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 5left → T1right → T2
T1: 1left → nullright → null
T2: 7left → T3right → T4
T3: 4left → nullright → null
T4: 8left → nullright → null

Pending exclusive bounds — stack top at right

T0: (−∞, +∞)

Infinity labels represent Java long sentinels beyond the int domain. They are display labels, not imprecise JavaScript long numbers. Every ancestor constraint survives in the interval.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":5,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":7,"left":"T3","right":"T4"},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":8,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","low":null,"high":null}]`
checked	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Bound(Node node, long low, long high) {}
 9     public static boolean valid(Node root) {
10         if (root == null) return true;
11         ArrayDeque<Bound> stack = new ArrayDeque<>();
12         stack.push(new Bound(root,Long.MIN_VALUE,Long.MAX_VALUE));
13         while (!stack.isEmpty()) {
14             Bound bound = stack.pop();
15             Node node = bound.node;
16             if (node.value <= bound.low || node.value >= bound.high) return false;
17             if (node.right != null) stack.push(new Bound(node.right,node.value,bound.high));
18             if (node.left != null) stack.push(new Bound(node.left,bound.low,node.value));
19         }
20         return true;
21     }
22     private static void inorder(Node node, List<Integer> values) {
23         if (node == null) return;
24         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
25     }
26     public static boolean baseline(Node root) {
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         for (int i = 1; i < values.size(); i++) if (values.get(i-1) >= values.get(i)) return false;
29         return true;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Use exclusive long bounds beyond the int domain.
null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.
treeNodes
[{"id":"T0","value":5,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":7,"left":"T3","right":"T4"},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":8,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","low":null,"high":null}]
checked
[]
phase
"initial"
current
null
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":5,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":7,"left":"T3","right":"T4"},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":8,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T2","low":5,"high":null},{"id":"T1","low":null,"high":5}]
checked
[{"id":"T0","low":null,"high":null,"passes":true}]
phase
"accept"
current
"T0"
bound
{"id":"T0","low":null,"high":null}
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":5,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":7,"left":"T3","right":"T4"},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":8,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T2","low":5,"high":null}]
checked
[{"id":"T0","low":null,"high":null,"passes":true},{"id":"T1","low":null,"high":5,"passes":true}]
phase
"accept"
current
"T1"
bound
{"id":"T1","low":null,"high":5}
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":5,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":7,"left":"T3","right":"T4"},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":8,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T4","low":7,"high":null},{"id":"T3","low":5,"high":7}]
checked
[{"id":"T0","low":null,"high":null,"passes":true},{"id":"T1","low":null,"high":5,"passes":true},{"id":"T2","low":5,"high":null,"passes":true}]
phase
"accept"
current
"T2"
bound
{"id":"T2","low":5,"high":null}
Reject the inherited strict-bound violation.
All ancestor constraints remain active, so a parent-only comparison cannot rescue this value.
treeNodes
[{"id":"T0","value":5,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":7,"left":"T3","right":"T4"},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":8,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T4","low":7,"high":null}]
checked
[{"id":"T0","low":null,"high":null,"passes":true},{"id":"T1","low":null,"high":5,"passes":true},{"id":"T2","low":5,"high":null,"passes":true},{"id":"T3","low":5,"high":7,"passes":false}]
phase
"reject"
current
"T3"
bound
{"id":"T3","low":5,"high":7}
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
false

Int extremes fit inside long boundaries

Input: [-2147483648,null,2147483647] · Result: true

Step 1 of 4: Use exclusive long bounds beyond the int domain.

null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.

BST validation — inherited exclusive intervals

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: -2147483648left → nullright → T1
T1: 2147483647left → nullright → null

Pending exclusive bounds — stack top at right

T0: (−∞, +∞)

Infinity labels represent Java long sentinels beyond the int domain. They are display labels, not imprecise JavaScript long numbers. Every ancestor constraint survives in the interval.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","low":null,"high":null}]`
checked	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Bound(Node node, long low, long high) {}
 9     public static boolean valid(Node root) {
10         if (root == null) return true;
11         ArrayDeque<Bound> stack = new ArrayDeque<>();
12         stack.push(new Bound(root,Long.MIN_VALUE,Long.MAX_VALUE));
13         while (!stack.isEmpty()) {
14             Bound bound = stack.pop();
15             Node node = bound.node;
16             if (node.value <= bound.low || node.value >= bound.high) return false;
17             if (node.right != null) stack.push(new Bound(node.right,node.value,bound.high));
18             if (node.left != null) stack.push(new Bound(node.left,bound.low,node.value));
19         }
20         return true;
21     }
22     private static void inorder(Node node, List<Integer> values) {
23         if (node == null) return;
24         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
25     }
26     public static boolean baseline(Node root) {
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         for (int i = 1; i < values.size(); i++) if (values.get(i-1) >= values.get(i)) return false;
29         return true;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Use exclusive long bounds beyond the int domain.
null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","low":null,"high":null}]
checked
[]
phase
"initial"
current
null
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T1","low":-2147483648,"high":null}]
checked
[{"id":"T0","low":null,"high":null,"passes":true}]
phase
"accept"
current
"T0"
bound
{"id":"T0","low":null,"high":null}
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
stack
[]
checked
[{"id":"T0","low":null,"high":null,"passes":true},{"id":"T1","low":-2147483648,"high":null,"passes":true}]
phase
"accept"
current
"T1"
bound
{"id":"T1","low":-2147483648,"high":null}
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
true

Duplicates violate strict ordering

Input: [2,2,3] · Result: false

Step 1 of 4: Use exclusive long bounds beyond the int domain.

null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.

BST validation — inherited exclusive intervals

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 2left → T1right → T2
T1: 2left → nullright → null
T2: 3left → nullright → null

Pending exclusive bounds — stack top at right

T0: (−∞, +∞)

Infinity labels represent Java long sentinels beyond the int domain. They are display labels, not imprecise JavaScript long numbers. Every ancestor constraint survives in the interval.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","low":null,"high":null}]`
checked	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Bound(Node node, long low, long high) {}
 9     public static boolean valid(Node root) {
10         if (root == null) return true;
11         ArrayDeque<Bound> stack = new ArrayDeque<>();
12         stack.push(new Bound(root,Long.MIN_VALUE,Long.MAX_VALUE));
13         while (!stack.isEmpty()) {
14             Bound bound = stack.pop();
15             Node node = bound.node;
16             if (node.value <= bound.low || node.value >= bound.high) return false;
17             if (node.right != null) stack.push(new Bound(node.right,node.value,bound.high));
18             if (node.left != null) stack.push(new Bound(node.left,bound.low,node.value));
19         }
20         return true;
21     }
22     private static void inorder(Node node, List<Integer> values) {
23         if (node == null) return;
24         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
25     }
26     public static boolean baseline(Node root) {
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         for (int i = 1; i < values.size(); i++) if (values.get(i-1) >= values.get(i)) return false;
29         return true;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Use exclusive long bounds beyond the int domain.
null bounds in this display mean unbounded below/above, not Java null long values. Actual Java sentinels lie outside the entire int domain.
treeNodes
[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","low":null,"high":null}]
checked
[]
phase
"initial"
current
null
Intersect the ancestor interval with this node’s side constraints.
Every child interval is exclusive. Duplicate values are rejected without value±1 arithmetic.
treeNodes
[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T2","low":2,"high":null},{"id":"T1","low":null,"high":2}]
checked
[{"id":"T0","low":null,"high":null,"passes":true}]
phase
"accept"
current
"T0"
bound
{"id":"T0","low":null,"high":null}
Reject the inherited strict-bound violation.
All ancestor constraints remain active, so a parent-only comparison cannot rescue this value.
treeNodes
[{"id":"T0","value":2,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":null},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T2","low":2,"high":null}]
checked
[{"id":"T0","low":null,"high":null,"passes":true},{"id":"T1","low":null,"high":2,"passes":false}]
phase
"reject"
current
"T1"
bound
{"id":"T1","low":null,"high":2}
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
false

Test the contract

Input: null
Output: true
Empty BST.
Input: [0,MIN,MAX]
Output: true
Full int domain.
Input: [5,1,7,null,null,4,8]
Output: false
Ancestor violation.
Input: [2,2,3]
Output: false
Strict duplicates policy.

Common mistakes and counterexamples

Check only child versus parent

Counterexample: 4 under the right subtree of 5 can pass its immediate-parent comparison.

Retain inherited lower and upper constraints.

Allow equality in either subtree

Counterexample: [2,2,3] violates this strict API.

Use <=low and >=high rejection.

Use int extreme values as exclusive infinity

Counterexample: A single MIN root would be rejected.

Use long bounds outside the entire int domain.

Follow-ups

Allow duplicates on one chosen side.

Specify an inclusive/exclusive endpoint policy per edge. Ordinary nondecreasing inorder order is insufficient to enforce which side owns equal values.

Return the violating ancestor.

Carry which ancestor owns each bound. A failed comparison can then report the exact inequality and identity, not just false.

Validate a comparator-based BST.

Require a consistent total order and define comparator equality semantics. Long sentinels become optional bounds rather than fabricated generic values.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 145/20,000 characters

Self-review

Can I state every frame’s open-interval meaning?Can I explain why parent-only checks are incomplete?Can I handle MIN/MAX without arithmetic overflow?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.