Loading…

mediumTreesAsked very often

Is This a Binary Search Tree?

Q: How do you solve Is This a Binary Search Tree? using the Brute Force — Validate Each Node Against Subtree Min/Max approach?

When to use it: Mention to anchor the definition: every left value < node < every right value. Then explain why it's O(n²) and how bounds fix it. The most literal translation of the definition: a node is valid if every value in its left subtree is strictly smaller and every value in its right subtree is strictly larger, and both subtrees are themselves valid BSTs. **How the check works.** For each node, compute the maximum value in its left subtree and the minimum value in its right subtree. The node is locally consistent only if `leftMax < node.value` and `node.value < rightMin` (strict, per HackerRank). Recurse into both children; the whole tree is a BST only if every node passes. **Why this is correct but slow.** Computing the min/max of a subtree means walking that entire subtree. Doing it at every node re-walks overlapping regions over and over. For a skewed tree, the top node scans n−1 descendants, the next scans n−2, and so on — the familiar n²/2 total. It's correct and a fine way to *explain* the invariant, but it wastes work the bounds approach avoids. **The key realization it leads to.** The min/max a node needs are exactly the bounds inherited from its ancestors. Instead of recomputing them bottom-up at every node, we can pass them top-down in O(1) — that's the optimal approach. Time complexity: O(n²). Space complexity: O(h).

Q: How do you solve Is This a Binary Search Tree? using the Top-Down Bounds — (low, high) Range (Optimal) approach?

When to use it: The answer they want. Carry a tightening open interval down the recursion; O(n). The brute force recomputes, at every node, the min/max that its ancestors already implicitly define. The optimization is to *pass those bounds down* instead of recomputing them. **The tightening interval.** Start at the root with an open interval (−∞, +∞) — the root may be anything. A node is valid iff `low < value < high` (strict, matching HackerRank's distinct-values rule). Then the children inherit narrowed intervals: - The **left** child must be smaller than this node, so its upper bound becomes `node.value`: range `(low, node.value)`. - The **right** child must be larger, so its lower bound becomes `node.value`: range `(node.value, high)`. Because the bounds accumulate down every path, a node is automatically checked against *all* its ancestors, not just its parent. The earlier counterexample — a `1` buried in the right subtree of `3` — is caught because by the time we reach `1`, its inherited `low` is `3`, and `3 < 1` is false. **Why strict matters here.** HackerRank's values are distinct, so the comparison is `low < value < high`. If duplicates were permitted on, say, the right, you'd relax that side to `value < high` becoming `value <= high` — but that's not this problem. **Sentinels.** Use `Long.MIN_VALUE`/`Long.MAX_VALUE` (or nullable bounds) so the root's unbounded interval can't accidentally reject a legitimate 0 or 10000. Since values fit in int, longs as sentinels are safe and simple. **Equivalent: strictly increasing inorder.** An inorder traversal of a valid BST yields values in strictly increasing order. Tracking the previous value and checking `prev < current` at each visit is an equally valid O(n) method — same idea, viewed as a stream. Time complexity: O(n). Space complexity: O(h).

Trees & BST · 33 of 41 · 9 min

Given the root of a binary tree, determine whether it is a valid binary search tree.

For every node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater. (HackerRank's version uses distinct values in the range 0 to 10000, so equality anywhere makes it invalid.)

Return true if the tree is a valid BST, otherwise false.

In plain English

A valid BST requires that EVERY node's value fits strictly within the open interval defined by its ancestors: bigger than every ancestor it sits to the right of, smaller than every ancestor it sits to the left of. Checking only direct children is insufficient — a node can satisfy its parent yet violate a grandparent.

Examples

Example 1

Input: tree with root 3, left subtree {2,1}, right subtree {5,4,6}
Output: true
Note: Inorder is 1 2 3 4 5 6 — strictly increasing, so it's a valid BST.

Example 2

Input: root 3 with right child 5 whose LEFT child is 1
Output: false
Note: 1 is in 3's right subtree but 1 < 3. The local 5>1 check passes, but the range check at 1 (must be > 3) fails.

Example 3

Input: root 2 with left child 2
Output: false
Note: Equal values are not allowed under HackerRank's strict rule — the left child must be strictly less than 2.

Constraints

1 ≤ number of nodes ≤ 10000
0 ≤ node value ≤ 10000
All node values are distinct
The BST property must hold strictly (no equal values allowed)

Clarifying questions4First question: Are duplicate values allowed?Explore questions

Q1.Are duplicate values allowed?
No. HackerRank uses distinct values 0..10000 and requires strict inequalities, so any equal value makes the tree invalid. If duplicates were allowed, you'd relax one side to ≤.
Q2.Is checking each node against its immediate children enough?
No — that's the classic trap. A node's left child could be valid locally but a deeper descendant on that side could exceed an ancestor's bound. The constraint is global.
Q3.What's the value range, and could bounds overflow?
Values are 0..10000, so int is safe. Using sentinel bounds like Long.MIN/MAX (or null) avoids edge issues if values ever reached Integer extremes.
Q4.Is an empty subtree a valid BST?
Yes — a null node trivially satisfies the property, which is the recursion's base case returning true.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A node being larger than its direct left child and smaller than its direct right child is NOT enough — every node must satisfy the invariant against ALL ancestors. The clean answer carries a (low, high) open interval down the recursion: a node's value must lie strictly between them, then recurse left with high = node.value and right with low = node.value. HackerRank uses STRICT inequalities (distinct values 0..10000), so equal values are invalid. O(n) time, O(h) space. The inorder traversal must be strictly increasing is the equivalent check.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize the BST property is global — every node constrained by all its ancestors — and can encode that with a tightening range or a strictly-increasing inorder check.

Where candidates slip

Only comparing each node to its immediate children, which passes invalid trees where a deep descendant violates an ancestor's bound. Also using <= when HackerRank requires strict <.

How to stand out

Call out the local-check trap explicitly, present the range recursion, then offer the inorder equivalent and note the strict-inequality requirement for distinct values.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Validate Each Node Against Subtree Min/Max	`O(n²)`	`O(h)`	Mention to anchor the definition: every left value < node < every right value. Then explain why it's O(n²) and how bounds fix it.	Read
2	Top-Down Bounds — (low, high) Range (Optimal)Optimal	`O(n)`	`O(h)`	The answer they want. Carry a tightening open interval down the recursion; O(n).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewnode, range (low, high)low < value < high?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Validate Each Node Against Subtree Min/Max

TimeO(n²)SpaceO(h)

Mention to anchor the definition: every left value < node < every right value. Then explain why it's O(n²) and how bounds fix it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Restate the invariant literally: at every node, the maximum of the left subtree must be < node and the minimum of the right subtree must be > node.

2Hint 2Explore hint

Write helpers that find the max and min of a subtree, and call them at every node.

3Hint 3Explore hint

Notice you re-scan subtrees repeatedly — that's the source of the quadratic cost the optimal approach removes.

A · Core idea

The most literal translation of the definition: a node is valid if every value in its left subtree is strictly smaller and every value in its right subtree is strictly larger, and both subtrees are themselves valid BSTs.

How the check works. For each node, compute the maximum value in its left subtree and the minimum value in its right subtree. The node is locally consistent only if leftMax < node.value and node.value < rightMin (strict, per HackerRank). Recurse into both children; the whole tree is a BST only if every node passes.

Why this is correct but slow. Computing the min/max of a subtree means walking that entire subtree. Doing it at every node re-walks overlapping regions over and over. For a skewed tree, the top node scans n−1 descendants, the next scans n−2, and so on — the familiar n²/2 total. It's correct and a fine way to explain the invariant, but it wastes work the bounds approach avoids.

The key realization it leads to. The min/max a node needs are exactly the bounds inherited from its ancestors. Instead of recomputing them bottom-up at every node, we can pass them top-down in O(1) — that's the optimal approach.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root 3, right child 5 whose left child is 1 (invalid)

Why the local check fails

How to read it:1 sits in 3's right subtree but 1 < 3 — only a subtree-wide (or bounds) check catches it.

Rendering diagram…

Final resultfalse

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the full code

solution.javaJava

Brute Force — Validate Each Node Against Subtree Min/Max — reference

3 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
}
7
 
8
public boolean checkBST(Node root) {
9
    if (root == null) return true;
10
    if (root.left != null && subtreeMax(root.left) >= root.data) return false;   // strict
11
    if (root.right != null && subtreeMin(root.right) <= root.data) return false; // strict
12
    // Both subtrees must independently be valid BSTs too.
13
    return checkBST(root.left) && checkBST(root.right);
14
}
15
 
16
private int subtreeMax(Node node) {
17
    int best = node.data;
18
    if (node.left != null) best = Math.max(best, subtreeMax(node.left));
19
    if (node.right != null) best = Math.max(best, subtreeMax(node.right));
20
    return best;
21
}
22
 
23
private int subtreeMin(Node node) {
24
    int best = node.data;
25
    if (node.left != null) best = Math.min(best, subtreeMin(node.left));
26
    if (node.right != null) best = Math.min(best, subtreeMin(node.right));
27
    return best;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n²) timeO(h) spaceOpen the invariant and proofExplore the proof

Stating 'leftMax < node < rightMin at every node' nails the definition, and the redundant subtree scans it forces are precisely what the top-down bounds version eliminates — a clean brute-to-optimal narrative.

ComplexityO(n²) time, O(h) space — At each of n nodes you scan its entire subtree to find min/max — O(n) per node in the worst (skewed) case → O(n²). The recursion stack is O(h).

E · Edge cases and pitfalls5Single node — No subtrees to scan → true.Explore edge cases

Edge cases handled

Single nodeNo subtrees to scan → true.
root 2 with left child 2subtreeMax(left)=2 >= 2 → false (strict).

Pitfalls

Using <= / >= incorrectly: HackerRank is strict, so equal values must fail.
Re-scanning subtrees at every node — O(n²), too slow at n = 10000 in the worst case.
Only comparing parent to direct child — misses deep violations entirely.

03.2

Approach 2 of 2 · Optimal

Top-Down Bounds — (low, high) Range (Optimal)

TimeO(n)SpaceO(h)

The answer they want. Carry a tightening open interval down the recursion; O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of recomputing each node's allowed min/max from its subtree, can the parent simply tell the child what range it's allowed to be in?

2Hint 2Explore hint

Pass a (low, high) open interval down. A node is valid only if low < value < high. What range do the children inherit?

3Hint 3Explore hint

Left child: the value becomes the new HIGH (everything left must be smaller). Right child: the value becomes the new LOW. Use sentinels (±∞) at the root.

A · Core idea

The brute force recomputes, at every node, the min/max that its ancestors already implicitly define. The optimization is to pass those bounds down instead of recomputing them.

The tightening interval. Start at the root with an open interval (−∞, +∞) — the root may be anything. A node is valid iff low < value < high (strict, matching HackerRank's distinct-values rule). Then the children inherit narrowed intervals:

The left child must be smaller than this node, so its upper bound becomes node.value: range (low, node.value).
The right child must be larger, so its lower bound becomes node.value: range (node.value, high).

Because the bounds accumulate down every path, a node is automatically checked against all its ancestors, not just its parent. The earlier counterexample — a 1 buried in the right subtree of 3 — is caught because by the time we reach 1, its inherited low is 3, and 3 < 1 is false.

Why strict matters here. HackerRank's values are distinct, so the comparison is low < value < high. If duplicates were permitted on, say, the right, you'd relax that side to value < high becoming value <= high — but that's not this problem.

Sentinels. Use Long.MIN_VALUE/Long.MAX_VALUE (or nullable bounds) so the root's unbounded interval can't accidentally reject a legitimate 0 or 10000. Since values fit in int, longs as sentinels are safe and simple.

Equivalent: strictly increasing inorder. An inorder traversal of a valid BST yields values in strictly increasing order. Tracking the previous value and checking prev < current at each visit is an equally valid O(n) method — same idea, viewed as a stream.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root 3, right child 5 whose left child is 1 (invalid)

Bounds threaded down [3 → 5 → 1]

How to read it:Node 1 inherits low = 3, so 3 < 1 fails and the tree is rejected.

Rendering diagram…

Final resultfalse

C · Code with teaching comments

solution.javaJava

Top-Down Bounds — (low, high) Range (Optimal) — optimal

4 teaching notes

1
public boolean checkBST(Node root) {
2
    // Root starts unbounded; sentinels avoid rejecting legitimate extreme values.
3
    return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
4
}
5
 
6
private boolean isBST(Node node, long low, long high) {
7
    if (node == null) return true;                 // empty subtree is valid
8
    if (node.data <= low || node.data >= high) {   // strict: must be inside (low, high)
9
        return false;
10
    }
11
    return isBST(node.left, low, node.data)        // left: high tightens to node
12
        && isBST(node.right, node.data, high);     // right: low tightens to node
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

The BST property is global, and the elegant way to enforce a global property locally is to thread context (the bounds) through the recursion. 'Each node narrows the legal interval for its descendants' is the one sentence that turns an O(n²) check into O(n).

ComplexityO(n) time, O(h) space — Each node is visited once and does an O(1) range check → O(n) time. The recursion stack is O(h): O(log n) balanced, O(n) skewed.

E · Edge cases and pitfalls6Single node — −∞ < value < +∞ → true.Explore edge cases

Edge cases handled

Single node−∞ < value < +∞ → true.
Strictly increasing right-skewed chainEach node's low rises, all pass → true.
Node equal to an ancestorHits node.data <= low or >= high → false (strict).

Pitfalls

Using int bounds and rejecting legitimate Integer.MIN/MAX values — use long or nullable sentinels.
Writing < where HackerRank needs strict and accidentally allowing equality (or vice versa).
Passing the parent's value as a bound to the WRONG child (swapping low/high).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean checkBST(Node root) { return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isBST(Node node, long low, long high) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Local parent-child check only

Verifying just node.left < node < node.right passes invalid trees where a deep descendant violates an ancestor. The property is global; bounds must be inherited.

Explore the code comparison

Don't write this

boolean isBST(Node n) {
    if (n == null) return true;
    if (n.left != null && n.left.data >= n.data) return false;
    if (n.right != null && n.right.data <= n.data) return false;
    return isBST(n.left) && isBST(n.right);   // misses deep violations
}

Write this instead

boolean isBST(Node n, long low, long high) {
    if (n == null) return true;
    if (n.data <= low || n.data >= high) return false;
    return isBST(n.left, low, n.data) && isBST(n.right, n.data, high);
}

Allowing equality

HackerRank's values are distinct and the rule is strict, so a node equal to a bound must fail. Using < instead of <= on the bound check would wrongly accept duplicates.

Explore the code comparison

Don't write this

if node.data < low or node.data > high:   # allows equality to a bound
    return False

Write this instead

if not (low < node.data < high):          # strict on both sides
    return False

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Validate the BST invariant with a tightening (low, high) range

Code pattern to memorize

isBST(node, low, high):
    if node is null: return true
    if not (low < node.value < high): return false
    return isBST(node.left, low, node.value)
       and isBST(node.right, node.value, high)

Rules to remember

1Check each node against an inherited range, not just its immediate children.
2Going left tightens the upper bound to the parent's value; going right tightens the lower bound.
3HackerRank wants strict inequalities — equal values make it NOT a BST (values are distinct 0..10000).
4Equivalent check: an inorder traversal of a BST is strictly increasing.
5Comparing only parent-to-direct-child is the classic wrong answer — it misses violations deeper down.

Use this pattern when

Verifying the BST property holds globally, not just locally
Any 'is this structure ordered correctly' check that needs ancestor context
Validating before relying on BST search/insert correctness

Choose another pattern when

Duplicates are allowed on one side → loosen one bound to ≤ (not HackerRank's case)
You only need the min/max of a subtree → a simpler aggregation, not full validation
The tree isn't a search tree at all → a different traversal problem

Interview takeaway

Validating a BST is about propagating bounds: each node narrows the legal interval for its descendants. The local parent-child check is a trap; the range-passing recursion (or a strictly-increasing inorder) is the correct, O(n) answer.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternValidate a global ordering invariant by threading a tightening (low, high) range down the recursion. Going left lowers the upper bound, going right raises the lower bound, so each node is checked against all ancestors in O(n). The strictly-increasing inorder traversal is the equivalent stream-based check; remember HackerRank's strict-inequality, distinct-value rule.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Validate Binary Search Tree
The LeetCode twin — same bounds recursion; watch its duplicate/equality convention.
Kth Smallest Element in a BST
Relies on the same inorder-is-sorted property a valid BST guarantees.
Recover Binary Search Tree
Coming soon
Two nodes are swapped; find them via the inorder sequence's out-of-order pairs.
Binary Search Tree: Insertion
Insertion preserves exactly the invariant this problem validates.

Same pattern

←

Binary Search Tree: Lowest Common Ancestor

Continue · Next problem

Swap Nodes [Algo]

mediumTreesAsked very often

Is This a Binary Search Tree?

Trees & BST · 33 of 41 · 9 min

Given the root of a binary tree, determine whether it is a valid binary search tree.

Return true if the tree is a valid BST, otherwise false.

In plain English

Examples

Example 1

Input: tree with root 3, left subtree {2,1}, right subtree {5,4,6}
Output: true
Note: Inorder is 1 2 3 4 5 6 — strictly increasing, so it's a valid BST.

Example 2

Input: root 3 with right child 5 whose LEFT child is 1
Output: false
Note: 1 is in 3's right subtree but 1 < 3. The local 5>1 check passes, but the range check at 1 (must be > 3) fails.

Example 3

Input: root 2 with left child 2
Output: false
Note: Equal values are not allowed under HackerRank's strict rule — the left child must be strictly less than 2.

Constraints

1 ≤ number of nodes ≤ 10000
0 ≤ node value ≤ 10000
All node values are distinct
The BST property must hold strictly (no equal values allowed)

Clarifying questions4First question: Are duplicate values allowed?Explore questions

Q1.Are duplicate values allowed?
No. HackerRank uses distinct values 0..10000 and requires strict inequalities, so any equal value makes the tree invalid. If duplicates were allowed, you'd relax one side to ≤.
Q2.Is checking each node against its immediate children enough?
No — that's the classic trap. A node's left child could be valid locally but a deeper descendant on that side could exceed an ancestor's bound. The constraint is global.
Q3.What's the value range, and could bounds overflow?
Values are 0..10000, so int is safe. Using sentinel bounds like Long.MIN/MAX (or null) avoids edge issues if values ever reached Integer extremes.
Q4.Is an empty subtree a valid BST?
Yes — a null node trivially satisfies the property, which is the recursion's base case returning true.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize the BST property is global — every node constrained by all its ancestors — and can encode that with a tightening range or a strictly-increasing inorder check.

Where candidates slip

Only comparing each node to its immediate children, which passes invalid trees where a deep descendant violates an ancestor's bound. Also using <= when HackerRank requires strict <.

How to stand out

Call out the local-check trap explicitly, present the range recursion, then offer the inorder equivalent and note the strict-inequality requirement for distinct values.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Validate Each Node Against Subtree Min/Max	`O(n²)`	`O(h)`	Mention to anchor the definition: every left value < node < every right value. Then explain why it's O(n²) and how bounds fix it.	Read
2	Top-Down Bounds — (low, high) Range (Optimal)Optimal	`O(n)`	`O(h)`	The answer they want. Carry a tightening open interval down the recursion; O(n).	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Validate Each Node Against Subtree Min/Max

TimeO(n²)SpaceO(h)

Mention to anchor the definition: every left value < node < every right value. Then explain why it's O(n²) and how bounds fix it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Restate the invariant literally: at every node, the maximum of the left subtree must be < node and the minimum of the right subtree must be > node.

2Hint 2Explore hint

Write helpers that find the max and min of a subtree, and call them at every node.

3Hint 3Explore hint

Notice you re-scan subtrees repeatedly — that's the source of the quadratic cost the optimal approach removes.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root 3, right child 5 whose left child is 1 (invalid)

Why the local check fails

How to read it:1 sits in 3's right subtree but 1 < 3 — only a subtree-wide (or bounds) check catches it.

Rendering diagram…

Final resultfalse

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the full code

solution.javaJava

Brute Force — Validate Each Node Against Subtree Min/Max — reference

3 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
}
7
 
8
public boolean checkBST(Node root) {
9
    if (root == null) return true;
10
    if (root.left != null && subtreeMax(root.left) >= root.data) return false;   // strict
11
    if (root.right != null && subtreeMin(root.right) <= root.data) return false; // strict
12
    // Both subtrees must independently be valid BSTs too.
13
    return checkBST(root.left) && checkBST(root.right);
14
}
15
 
16
private int subtreeMax(Node node) {
17
    int best = node.data;
18
    if (node.left != null) best = Math.max(best, subtreeMax(node.left));
19
    if (node.right != null) best = Math.max(best, subtreeMax(node.right));
20
    return best;
21
}
22
 
23
private int subtreeMin(Node node) {
24
    int best = node.data;
25
    if (node.left != null) best = Math.min(best, subtreeMin(node.left));
26
    if (node.right != null) best = Math.min(best, subtreeMin(node.right));
27
    return best;
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n²) timeO(h) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(h) space — At each of n nodes you scan its entire subtree to find min/max — O(n) per node in the worst (skewed) case → O(n²). The recursion stack is O(h).

E · Edge cases and pitfalls5Single node — No subtrees to scan → true.Explore edge cases

Edge cases handled

Single nodeNo subtrees to scan → true.
root 2 with left child 2subtreeMax(left)=2 >= 2 → false (strict).

Pitfalls

Using <= / >= incorrectly: HackerRank is strict, so equal values must fail.
Re-scanning subtrees at every node — O(n²), too slow at n = 10000 in the worst case.
Only comparing parent to direct child — misses deep violations entirely.

03.2

Approach 2 of 2 · Optimal

Top-Down Bounds — (low, high) Range (Optimal)

TimeO(n)SpaceO(h)

The answer they want. Carry a tightening open interval down the recursion; O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of recomputing each node's allowed min/max from its subtree, can the parent simply tell the child what range it's allowed to be in?

2Hint 2Explore hint

Pass a (low, high) open interval down. A node is valid only if low < value < high. What range do the children inherit?

3Hint 3Explore hint

Left child: the value becomes the new HIGH (everything left must be smaller). Right child: the value becomes the new LOW. Use sentinels (±∞) at the root.

A · Core idea

The brute force recomputes, at every node, the min/max that its ancestors already implicitly define. The optimization is to pass those bounds down instead of recomputing them.

The left child must be smaller than this node, so its upper bound becomes node.value: range (low, node.value).
The right child must be larger, so its lower bound becomes node.value: range (node.value, high).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root 3, right child 5 whose left child is 1 (invalid)

Bounds threaded down [3 → 5 → 1]

How to read it:Node 1 inherits low = 3, so 3 < 1 fails and the tree is rejected.

Rendering diagram…

Final resultfalse

C · Code with teaching comments

solution.javaJava

Top-Down Bounds — (low, high) Range (Optimal) — optimal

4 teaching notes

1
public boolean checkBST(Node root) {
2
    // Root starts unbounded; sentinels avoid rejecting legitimate extreme values.
3
    return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
4
}
5
 
6
private boolean isBST(Node node, long low, long high) {
7
    if (node == null) return true;                 // empty subtree is valid
8
    if (node.data <= low || node.data >= high) {   // strict: must be inside (low, high)
9
        return false;
10
    }
11
    return isBST(node.left, low, node.data)        // left: high tightens to node
12
        && isBST(node.right, node.data, high);     // right: low tightens to node
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(h) space — Each node is visited once and does an O(1) range check → O(n) time. The recursion stack is O(h): O(log n) balanced, O(n) skewed.

E · Edge cases and pitfalls6Single node — −∞ < value < +∞ → true.Explore edge cases

Edge cases handled

Single node−∞ < value < +∞ → true.
Strictly increasing right-skewed chainEach node's low rises, all pass → true.
Node equal to an ancestorHits node.data <= low or >= high → false (strict).

Pitfalls

Using int bounds and rejecting legitimate Integer.MIN/MAX values — use long or nullable sentinels.
Writing < where HackerRank needs strict and accidentally allowing equality (or vice versa).
Passing the parent's value as a bound to the WRONG child (swapping low/high).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean checkBST(Node root) { return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isBST(Node node, long low, long high) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Local parent-child check only

Verifying just node.left < node < node.right passes invalid trees where a deep descendant violates an ancestor. The property is global; bounds must be inherited.

Explore the code comparison

Don't write this

boolean isBST(Node n) {
    if (n == null) return true;
    if (n.left != null && n.left.data >= n.data) return false;
    if (n.right != null && n.right.data <= n.data) return false;
    return isBST(n.left) && isBST(n.right);   // misses deep violations
}

Write this instead

boolean isBST(Node n, long low, long high) {
    if (n == null) return true;
    if (n.data <= low || n.data >= high) return false;
    return isBST(n.left, low, n.data) && isBST(n.right, n.data, high);
}

Allowing equality

HackerRank's values are distinct and the rule is strict, so a node equal to a bound must fail. Using < instead of <= on the bound check would wrongly accept duplicates.

Explore the code comparison

Don't write this

if node.data < low or node.data > high:   # allows equality to a bound
    return False

Write this instead

if not (low < node.data < high):          # strict on both sides
    return False

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Validate the BST invariant with a tightening (low, high) range

Code pattern to memorize

isBST(node, low, high):
    if node is null: return true
    if not (low < node.value < high): return false
    return isBST(node.left, low, node.value)
       and isBST(node.right, node.value, high)

Rules to remember

1Check each node against an inherited range, not just its immediate children.
2Going left tightens the upper bound to the parent's value; going right tightens the lower bound.
3HackerRank wants strict inequalities — equal values make it NOT a BST (values are distinct 0..10000).
4Equivalent check: an inorder traversal of a BST is strictly increasing.
5Comparing only parent-to-direct-child is the classic wrong answer — it misses violations deeper down.

Use this pattern when

Verifying the BST property holds globally, not just locally
Any 'is this structure ordered correctly' check that needs ancestor context
Validating before relying on BST search/insert correctness

Choose another pattern when

Duplicates are allowed on one side → loosen one bound to ≤ (not HackerRank's case)
You only need the min/max of a subtree → a simpler aggregation, not full validation
The tree isn't a search tree at all → a different traversal problem

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Validate Binary Search Tree
The LeetCode twin — same bounds recursion; watch its duplicate/equality convention.
Kth Smallest Element in a BST
Relies on the same inorder-is-sorted property a valid BST guarantees.
Recover Binary Search Tree
Coming soon
Two nodes are swapped; find them via the inorder sequence's out-of-order pairs.
Binary Search Tree: Insertion
Insertion preserves exactly the invariant this problem validates.

Same pattern

←

Binary Search Tree: Lowest Common Ancestor

Continue · Next problem

Swap Nodes [Algo]