These are the notes for DSA episode 39. A binary search tree (BST) keeps smaller values on the left and bigger values on the right, for the whole subtree of every node. We solve two classic interview problems on it. Validate Binary Search Tree (LeetCode 98): the check most people write first (each node against its two children) runs fine and gives a wrong answer; a correct brute force (each node against the max and min of its subtrees) times out on a big tree; the fix passes a (low, high) range down the tree and checks every node once, in O(n). Kth Smallest Element in a BST (LeetCode 230): sorting all values works, but an inorder walk is already sorted, so counting nodes and stopping at k takes only O(h + k). Every program below was run with javac 21 (8-second time limit, like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
Picture a library where every book has a number, and the shelves are arranged like a tree. At every shelf, smaller numbers go to the left wing, bigger numbers go to the right wing. Finding book 60 is quick: at each shelf, ask "smaller or bigger?" and go left or right. You never search the whole library.
Then a new helper files book 3. He puts it to the left of shelf 6, because 3 < 6. Locally it looks fine. But shelf 6 is in the "bigger than 5" wing, so book 3 is now lost: anyone searching for it goes left at shelf 5 and never finds it. The librarian's question, "is every book where the rule says it should be?", is exactly Validate BST.
| In the library | In a BST |
|---|---|
| A shelf with a number | a node with a value |
| The left wing / right wing of a shelf | the left subtree / right subtree |
| Smaller left, bigger right, for the whole wing | the BST property |
| A book filed in the wrong wing | a node that breaks the property (maybe deep down) |
| Walking left wing, shelf, right wing | inorder traversal: numbers come out sorted |
| "Give me the 3rd smallest book" | kth smallest element |
Binary search tree, from zero
- Binary tree: every node has at most two children,
leftandright(episode 36). - Subtree: a node's left subtree is its left child plus everything below that child; the same on the right.
- Binary search tree (BST): for every node, every value in its left subtree is smaller than the node, and every value in its right subtree is bigger.
- The rule is about the whole subtree, not just the two children. A grandchild can break it.
- Duplicates: in LeetCode 98, smaller and bigger are strict (
<and>), so two equal values make the tree invalid. Some textbooks allow duplicates on one side (for example<=on the left); always ask which rule the interviewer means. - Inorder traversal (left, node, right) of a BST visits the values in sorted order: everything smaller is visited before the node, everything bigger after it. Episode 36 promised this; here it pays off.
The shelf tree used everywhere below:
50
/ \
30 70
/ \ / \
20 40 60 80
Inorder: 20 30 40 50 60 70 80.
The trap tree (the misfiled book):
5
/ \
4 6
/ \
3 7
Every parent/child pair looks fine (4 < 5 < 6, 3 < 6 < 7), but 3 is in the right subtree of 5 and 3 < 5. Not a BST.
Problem 1: Validate Binary Search Tree (LeetCode 98)
Given the root of a binary tree, return true if it is a valid BST, otherwise false.
shelf tree → true
trap tree 5 → (4, 6 → (3, 7)) → false
empty tree (null) → true
one node → true
2 with a left child 2 → false (duplicates are not allowed)
one node with Integer.MAX_VALUE → true
The tempting check (wrong)
Compare each node only with its two children:
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static boolean naive(Node n) {
if (n == null) return true;
if (n.left != null && n.left.val >= n.val) return false;
if (n.right != null && n.right.val <= n.val) return false;
return naive(n.left) && naive(n.right);
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
Node trap = new Node(5, new Node(4),
new Node(6, new Node(3), new Node(7)));
System.out.println(naive(shelf));
System.out.println(naive(trap));
}
}
Real output:
true
true
The second line is wrong: the trap tree is not a BST. No error, no crash, just a wrong answer. At node 6 the check only sees 3 and 7; nobody compares 3 with 5.
Brute force: compare with the whole subtree
Do what the definition says: for every node, the maximum of its whole left subtree must be smaller than the node, and the minimum of its whole right subtree must be bigger.
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int max(Node n) {
if (n == null) return Integer.MIN_VALUE;
return Math.max(n.val, Math.max(max(n.left), max(n.right)));
}
static int min(Node n) {
if (n == null) return Integer.MAX_VALUE;
return Math.min(n.val, Math.min(min(n.left), min(n.right)));
}
static boolean brute(Node n) {
if (n == null) return true;
if (n.left != null && max(n.left) >= n.val) return false;
if (n.right != null && min(n.right) <= n.val) return false;
return brute(n.left) && brute(n.right);
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
Node trap = new Node(5, new Node(4),
new Node(6, new Node(3), new Node(7)));
System.out.println(brute(shelf));
System.out.println(brute(trap));
}
}
Real output:
true
false
Correct. At node 5, min(right subtree) = 3, which is not bigger than 5. The n.left != null checks matter: an empty subtree returns Integer.MIN_VALUE / Integer.MAX_VALUE, and we must not compare those with a node that really holds such a value.
The big input: Time Limit Exceeded
A balanced BST of the values 1 to 10,00,000 (always the middle value on top, height 20), with a chain of 5,000 bigger shelves stacked on top, each one the left child of the next. It is still a valid BST, about 10,05,000 nodes and about 5,020 levels.
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int max(Node n) {
if (n == null) return Integer.MIN_VALUE;
return Math.max(n.val, Math.max(max(n.left), max(n.right)));
}
static int min(Node n) {
if (n == null) return Integer.MAX_VALUE;
return Math.min(n.val, Math.min(min(n.left), min(n.right)));
}
static boolean brute(Node n) {
if (n == null) return true;
if (n.left != null && max(n.left) >= n.val) return false;
if (n.right != null && min(n.right) <= n.val) return false;
return brute(n.left) && brute(n.right);
}
static Node balanced(int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi) / 2;
return new Node(mid, balanced(lo, mid - 1), balanced(mid + 1, hi));
}
static Node bigTree() {
Node root = balanced(1, 1_000_000);
for (int i = 1; i <= 5000; i++)
root = new Node(2_000_000 + i, root, null);
return root;
}
public static void main(String[] args) {
Node big = bigTree();
long t0 = System.nanoTime();
boolean ok = brute(big);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(ok + ", " + ms + " ms");
}
}
Real result: Time Limit Exceeded in the 8-second compiler. Run locally with no limit, it printed true, 22816 ms (and true, 22302 ms on a second run).
Why the brute force is slow
Every node calls max or min, which visits its entire subtree again. Each of the 5,000 chain shelves rescans the 10 lakh nodes below it: about 5,000 × 10,00,000 = 500 crore visits. In general the cost is the sum of all subtree sizes, which is O(n · h); on a fully skewed tree (a single line, h = n) it is O(n²).
Why not just use a single line of 10 lakh nodes? Because recursion that deep crashes. Java's call stack only holds a few thousand recursive calls with the default settings: in a test on my machine, a plain chain of 10,000 nodes already threw java.lang.StackOverflowError on the first call, while the 5,020-level tree above ran fine. Tall trees are dangerous for recursive code.
The key insight: pass a (low, high) range down
Walk down like the librarian:
- The root may hold any value: range (−∞, +∞).
- Stepping into the left subtree of a node with value
v, every value must be belowv: range (low, v). Stepping right: range (v, high). - A node is fine only if low < val < high. The range already remembers the rules of all its ancestors, so one check per node is enough: O(n).
| Node | Range it receives | Check |
|---|---|---|
| 5 | (−∞, +∞) | ok |
| 4 | (−∞, 5) | ok |
| 6 | (5, +∞) | ok |
| 3 | (5, 6) | 3 is not above 5: false |
| 7 | (6, +∞) | (never needed) |
What is −∞ in Java? If you use Integer.MIN_VALUE and Integer.MAX_VALUE as the bounds, a node that holds exactly one of those values fails val > low or val < high. Use long bounds (Long.MIN_VALUE, Long.MAX_VALUE), which lie outside every int, or use null to mean "no bound" (Integer parameters).
A second O(n) way: an inorder walk of a BST is sorted, so the tree is valid exactly when each inorder value is strictly bigger than the previous one (see Practice 1).
The optimal solution in Java
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static boolean valid(Node n, long low, long high) {
if (n == null) return true;
if (n.val <= low || n.val >= high) return false;
return valid(n.left, low, n.val) && valid(n.right, n.val, high);
}
static boolean isValidBST(Node root) {
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
Node trap = new Node(5, new Node(4),
new Node(6, new Node(3), new Node(7)));
System.out.println(isValidBST(shelf));
System.out.println(isValidBST(trap));
System.out.println(isValidBST(null));
System.out.println(isValidBST(new Node(7)));
System.out.println(isValidBST(new Node(2, new Node(2), null)));
System.out.println(isValidBST(new Node(Integer.MAX_VALUE)));
}
}
Real output:
true
false
true
true
false
true
Shelf true, trap false, empty true, one node true, duplicate false, Integer.MAX_VALUE node true.
The big tree:
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static boolean valid(Node n, long low, long high) {
if (n == null) return true;
if (n.val <= low || n.val >= high) return false;
return valid(n.left, low, n.val) && valid(n.right, n.val, high);
}
static boolean isValidBST(Node root) {
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
static Node balanced(int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi) / 2;
return new Node(mid, balanced(lo, mid - 1), balanced(mid + 1, hi));
}
static Node bigTree() {
Node root = balanced(1, 1_000_000);
for (int i = 1; i <= 5000; i++)
root = new Node(2_000_000 + i, root, null);
return root;
}
public static void main(String[] args) {
Node big = bigTree();
long t0 = System.nanoTime();
boolean ok = isValidBST(big);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(ok + ", " + ms + " ms");
}
}
Real output: true, 9 ms (7 to 10 ms across runs). The same tree took about 22,800 ms with the brute force: more than two thousand times faster.
Problem 2: Kth Smallest Element in a BST (LeetCode 230)
Given the root of a BST and an integer k (1-based: k = 1 is the smallest), return the kth smallest value.
shelf tree, k = 1 → 20
shelf tree, k = 3 → 40
shelf tree, k = 7 → 80
Brute force: collect everything and sort
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static void collect(Node n, List<Integer> out) {
if (n == null) return;
out.add(n.val);
collect(n.left, out);
collect(n.right, out);
}
static int kthBrute(Node root, int k) {
List<Integer> all = new ArrayList<>();
collect(root, all);
Collections.sort(all);
return all.get(k - 1);
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
System.out.println(kthBrute(shelf, 1));
System.out.println(kthBrute(shelf, 3));
System.out.println(kthBrute(shelf, 7));
}
}
Real output:
20
40
80
Correct, but it visits every node, stores every value (O(n) space) and sorts them (O(n log n)), just to read one.
Optimal: inorder with a counter that stops at k
Inorder visits a BST in sorted order, so the kth node visited is the answer. Keep one shared counter; stop as soon as it reaches k.
Trace for k = 3: the walk goes left 50 → 30 → 20; visit 20 (count 1), back to 30 (count 2), then 40 (count 3 = k, answer 40, stop). 50, 60, 70 and 80 are never visited. The work is the walk down to the smallest node (h steps) plus k visits: O(h + k).
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int count, answer;
static void walk(Node n, int k) {
if (n == null || count >= k) return;
walk(n.left, k);
if (count >= k) return;
count++;
if (count == k) answer = n.val;
walk(n.right, k);
}
static int kthSmallest(Node root, int k) {
count = 0;
answer = -1;
walk(root, k);
return answer;
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
System.out.println(kthSmallest(shelf, 1));
System.out.println(kthSmallest(shelf, 3));
System.out.println(kthSmallest(shelf, 7));
System.out.println(kthSmallest(new Node(9), 1));
}
}
Real output:
20
40
80
9
count and answer are static fields, so every recursive call shares them. kthSmallest resets them on every call.
The big tree, k = 5:
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int count, answer;
static void walk(Node n, int k) {
if (n == null || count >= k) return;
walk(n.left, k);
if (count >= k) return;
count++;
if (count == k) answer = n.val;
walk(n.right, k);
}
static int kthSmallest(Node root, int k) {
count = 0;
answer = -1;
walk(root, k);
return answer;
}
static Node balanced(int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi) / 2;
return new Node(mid, balanced(lo, mid - 1), balanced(mid + 1, hi));
}
static Node bigTree() {
Node root = balanced(1, 1_000_000);
for (int i = 1; i <= 5000; i++)
root = new Node(2_000_000 + i, root, null);
return root;
}
public static void main(String[] args) {
Node big = bigTree();
long t0 = System.nanoTime();
int x = kthSmallest(big, 5);
long us = (System.nanoTime() - t0) / 1000;
System.out.println(x + ", " + us + " us");
}
}
Real output: 5, 639 us (well under a millisecond). It walked down about 5,020 levels to the value 1, then counted 5 nodes. Timing both methods in one program (kthBrute and kthSmallest on the same big tree) printed:
sort all: 5, 225276 us
inorder: 5, 3661 us
(The inorder time includes the JIT warming up; on its own it ran in about 0.6 ms.) Sorting ten lakh values took about a quarter of a second.
The same code in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node *left, *right;
Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};
bool valid(Node* n, long long low, long long high) {
if (!n) return true;
if (n->val <= low || n->val >= high) return false;
return valid(n->left, low, n->val) && valid(n->right, n->val, high);
}
bool isValidBST(Node* root) { return valid(root, LLONG_MIN, LLONG_MAX); }
void walk(Node* n, int k, int& count, int& answer) { // count shared by reference
if (!n || count >= k) return;
walk(n->left, k, count, answer);
if (count >= k) return;
if (++count == k) answer = n->val;
walk(n->right, k, count, answer);
}
int kthSmallest(Node* root, int k) {
int count = 0, answer = -1;
walk(root, k, count, answer);
return answer;
}
int main() {
Node* shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
Node* trap = new Node(5, new Node(4), new Node(6, new Node(3), new Node(7)));
cout << boolalpha;
cout << isValidBST(shelf) << ' ' << isValidBST(trap) << ' ' << isValidBST(nullptr) << ' '
<< isValidBST(new Node(2, new Node(2))) << ' ' << isValidBST(new Node(INT_MAX)) << '\n';
cout << kthSmallest(shelf, 1) << ' ' << kthSmallest(shelf, 3) << ' ' << kthSmallest(shelf, 7) << '\n';
}
Real output (g++ -O2):
true false true false true
20 40 80
In C++, long long bounds (LLONG_MIN, LLONG_MAX) play the role of Java's long, and the counter is shared by passing it by reference (int& count).
The same code in Python
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_valid_bst(root):
def valid(n, low, high): # Python ints never overflow: use -inf / +inf
if n is None:
return True
if not (low < n.val < high):
return False
return valid(n.left, low, n.val) and valid(n.right, n.val, high)
return valid(root, float("-inf"), float("inf"))
def kth_smallest(root, k):
count = 0
def walk(n):
nonlocal count # share ONE counter with every call
if n is None or count >= k:
return None
found = walk(n.left)
if found is not None:
return found
count += 1
if count == k:
return n.val
return walk(n.right)
return walk(root)
shelf = Node(50, Node(30, Node(20), Node(40)), Node(70, Node(60), Node(80)))
trap = Node(5, Node(4), Node(6, Node(3), Node(7)))
print(is_valid_bst(shelf), is_valid_bst(trap), is_valid_bst(None),
is_valid_bst(Node(2, Node(2))), is_valid_bst(Node(2**31 - 1)))
print(kth_smallest(shelf, 1), kth_smallest(shelf, 3), kth_smallest(shelf, 7))
Real output:
True False True False True
20 40 80
Python integers never overflow, so float("-inf") and float("inf") are safe bounds, and low < n.val < high is a chained comparison. nonlocal count makes the inner function share one counter. Python's default recursion limit is 1,000, so a very tall tree needs sys.setrecursionlimit or an iterative version with a stack.
Three real bugs
Bug 1: int bounds
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static boolean valid(Node n, int low, int high) {
if (n == null) return true;
if (n.val <= low || n.val >= high) return false;
return valid(n.left, low, n.val) && valid(n.right, n.val, high);
}
static boolean isValidBST(Node root) {
return valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
System.out.println(isValidBST(shelf));
System.out.println(isValidBST(new Node(Integer.MAX_VALUE)));
}
}
Real output:
true
false
A single node is always a valid BST, but its value equals high (Integer.MAX_VALUE), so n.val >= high is true and the answer is false. LeetCode has exactly this test. Use long bounds or null.
Bug 2: the counter as a parameter
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int answer;
static void walk(Node n, int k, int count) {
if (n == null) return;
walk(n.left, k, count);
count++;
if (count == k) answer = n.val;
walk(n.right, k, count);
}
static int kthSmallest(Node root, int k) {
answer = -1;
walk(root, k, 0);
return answer;
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
System.out.println(kthSmallest(shelf, 3));
}
}
Real output: 80 (it should be 40). Java passes an int by value: every call gets its own copy of count, and the counting done inside the left subtree is lost when that call returns. Here the count at each node only grows by the number of right turns on the way down, so 80 (two right turns from 50) is the first to reach 3. Keep the counter in one shared place: a static field, a field of an object, or an int[] count = new int[1].
Bug 3: the counter never reset
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int count, answer;
static void walk(Node n, int k) {
if (n == null || count >= k) return;
walk(n.left, k);
if (count >= k) return;
count++;
if (count == k) answer = n.val;
walk(n.right, k);
}
static int kthSmallest(Node root, int k) {
answer = -1;
walk(root, k);
return answer;
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
System.out.println(kthSmallest(shelf, 1));
System.out.println(kthSmallest(shelf, 3));
}
}
Real output:
20
30
The first call leaves count = 1, so the second call starts counting from 1 and stops at the 2nd smallest value. Judges like LeetCode run many test cases in the same program, so this fails there too. Reset shared state (count = 0;) at the start of every call.
Complexity
| Algorithm | Time | Extra space | Big tree (10,05,000 nodes) |
|---|---|---|---|
| Validate: children only (wrong) | O(n) | O(h) | wrong answer on the trap tree |
| Validate: subtree max / min | O(n · h), O(n²) if skewed | O(h) recursion | 22.8 s, Time Limit Exceeded |
| Validate: (low, high) range | O(n) | O(h) recursion | 9 ms |
| Validate: inorder, strictly increasing | O(n) | O(h) recursion | |
| Kth: collect + sort | O(n log n) | O(n) list | about 225 ms |
| Kth: inorder + counter | O(h + k) | O(h) recursion | under 1 ms |
h is the height: about log₂ n for a balanced tree, up to n for a skewed one.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Comparing a node only with its children | true for the trap tree 5 → (4, 6 → (3, 7)) |
a grandchild can break the rule | pass (low, high) down |
int bounds Integer.MIN_VALUE / Integer.MAX_VALUE |
false for new Node(Integer.MAX_VALUE) |
the value sits exactly on the bound | long bounds, or null |
Allowing equal values: n.val < low \|\| n.val > high |
true for 2 → left 2 |
duplicates must be rejected (LeetCode 98) | n.val <= low \|\| n.val >= high returns false |
Counter passed as int count |
kthSmallest(shelf, 3) → 80 |
each call has its own copy | a shared static field or int[] |
| Counter never reset | k = 1 then k = 3 → 20, 30 |
count starts where the last call stopped | count = 0; at the start |
max(n.left) >= n.val without n.left != null |
false for a node holding Integer.MIN_VALUE with an empty left side |
the empty subtree's sentinel equals the value | check the child exists first |
| Very tall tree with recursion | java.lang.StackOverflowError |
one stack frame per level | iterative version with an explicit stack |
Mini project: the library audit
Build a library BST from a list of book numbers by inserting them one by one (see Practice 4). Then "misfile" one book by changing a node's value directly. Write audit(Node n, long low, long high) that prints every misfiled book together with the range it should have been in, like book 3 is misfiled: must be in (5, 6), and returns how many it found. Finally, print the library in shelf order with an inorder walk, and the 3rd smallest and 3rd largest book numbers.
Practice
- Validate with inorder and a previous value.
Solution
Walk inorder, remember the previous value (Integer prev, null at the start), and fail if the current value is not strictly bigger. Using null instead of a sentinel means a node with Integer.MIN_VALUE works.
static Integer prev;
static boolean inorderValid(Node n) {
if (n == null) return true;
if (!inorderValid(n.left)) return false;
if (prev != null && n.val <= prev) return false;
prev = n.val;
return inorderValid(n.right);
}
static boolean isValidBST(Node root) {
prev = null;
return inorderValid(root);
}
Shelf → true, trap → false, new Node(Integer.MIN_VALUE) → true (real output: true false true).
- Kth largest element.
Solution
Reverse inorder (right, node, left) visits from the biggest down. Same counter.
static void back(Node n, int k) {
if (n == null || count >= k) return;
back(n.right, k);
if (count >= k) return;
count++;
if (count == k) answer = n.val;
back(n.left, k);
}
Shelf, k = 1 → 80; k = 3 → 60 (real output: 80 60).
- Search in a BST (LeetCode 700).
Solution
At each node go left if the target is smaller, right if bigger: O(h), no recursion needed.
static Node search(Node n, int x) {
while (n != null && n.val != x) n = x < n.val ? n.left : n.right;
return n;
}
search(shelf, 60).val → 60, search(shelf, 65) → null.
- Insert into a BST (LeetCode 701).
Solution
Walk down as in search; where you fall off the tree, attach a new node.
static Node insert(Node n, int x) {
if (n == null) return new Node(x);
if (x < n.val) n.left = insert(n.left, x);
else n.right = insert(n.right, x);
return n;
}
After insert(shelf, 65) (it becomes the right child of 60), search(shelf, 65).val → 65 and isValidBST(shelf) → true (real output: 65 true).
All four were run together in one program:
Full practice program and output
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Integer prev;
static boolean inorderValid(Node n) {
if (n == null) return true;
if (!inorderValid(n.left)) return false;
if (prev != null && n.val <= prev) return false;
prev = n.val;
return inorderValid(n.right);
}
static boolean isValidBST(Node root) {
prev = null;
return inorderValid(root);
}
static int count, answer;
static void back(Node n, int k) {
if (n == null || count >= k) return;
back(n.right, k);
if (count >= k) return;
count++;
if (count == k) answer = n.val;
back(n.left, k);
}
static int kthLargest(Node root, int k) {
count = 0;
answer = -1;
back(root, k);
return answer;
}
static Node search(Node n, int x) {
while (n != null && n.val != x) n = x < n.val ? n.left : n.right;
return n;
}
static Node insert(Node n, int x) {
if (n == null) return new Node(x);
if (x < n.val) n.left = insert(n.left, x);
else n.right = insert(n.right, x);
return n;
}
public static void main(String[] args) {
Node shelf = new Node(50, new Node(30, new Node(20), new Node(40)),
new Node(70, new Node(60), new Node(80)));
Node trap = new Node(5, new Node(4),
new Node(6, new Node(3), new Node(7)));
System.out.println(isValidBST(shelf) + " " + isValidBST(trap) + " " + isValidBST(new Node(Integer.MIN_VALUE)));
System.out.println(kthLargest(shelf, 1) + " " + kthLargest(shelf, 3));
System.out.println(search(shelf, 60).val + " " + search(shelf, 65));
insert(shelf, 65);
System.out.println(search(shelf, 65).val + " " + isValidBST(shelf));
}
}
Real output:
true false true
80 60
60 null
65 true
Quick quiz
// 10 → left 5, right 15
// 5 → right 12
isValidBST(root) // ?
true (12 > 5), false (12 must be below 10), true (every child is in order), or StackOverflowError?
Answer
false. 12 is bigger than its parent 5, so the children-only check passes, but 12 is in 10's left subtree, so it must be below 10. Its range is (5, 10), and 12 is outside it.
Interview questions
- Why is "left child < node < right child" not enough? The BST property is about whole subtrees; a grandchild can be on the wrong side of an ancestor (the trap tree).
- What is the time and space of the range method? O(n) time, O(h) space for the recursion.
- Why
longbounds instead ofInteger.MIN_VALUE/MAX_VALUE? A node may hold exactly those values; the strict check would wrongly reject it.longbounds (ornull) lie outside everyint. - How do duplicates change the check? LeetCode 98 forbids them (strict
<,>). If duplicates were allowed on the left, the left range would become(low, v]. - Why is inorder of a BST sorted? Inorder visits the left subtree (all smaller), then the node, then the right subtree (all bigger), at every node.
- Kth smallest time? O(h + k) with early stopping; O(n) if you walk the whole tree.
- Follow-up: the BST changes often and kth smallest is asked often. Store in every node the size of its left subtree; then the kth smallest is found in O(h) by going left or right, like a binary search.
- What can go wrong with recursion on a skewed tree?
StackOverflowError; use an iterative inorder with an explicit stack.
Glossary
| Term | Meaning |
|---|---|
| Binary tree | A tree where every node has at most two children, left and right |
| Node | One item of the tree: a value plus left and right references |
| Subtree | A node's child plus everything below that child |
| Binary search tree (BST) | A binary tree where, at every node, all values in the left subtree are smaller and all values in the right subtree are bigger |
| BST property | The "smaller left, bigger right" rule, for whole subtrees |
| Duplicates rule | Whether equal values are allowed; LeetCode 98: not allowed (strict < and >) |
| Skewed tree | A tree that is (almost) a single line, so its height is close to n |
| Balanced tree | A tree whose height is about log₂ n |
| Height (h) | Number of levels of the tree |
| Inorder traversal | Visit left subtree, node, right subtree; sorted order in a BST |
| Reverse inorder | Right, node, left; descending order in a BST |
| Range (low, high) | The open interval a node's value must lie in, built from its ancestors |
| Sentinel | A special value used as a bound or marker, like Long.MIN_VALUE for −∞ |
Integer.MIN_VALUE / Integer.MAX_VALUE |
The smallest and biggest int: −2,147,483,648 and 2,147,483,647 |
long |
Java's 64-bit integer; holds every int and more |
| Pass by value | Java copies primitives like int into each call, so a callee's changes are not seen by the caller |
| Static field | A variable that belongs to the class; shared by every call |
| Kth smallest | The value that would be at position k (1-based) if all values were sorted |
| O(h + k) | Time that grows with the height plus k, not with the whole tree |
| Brute force | The straightforward, correct but slow solution |
| Time Limit Exceeded (TLE) | The judge stopped the program for running too long (8 s here) |
StackOverflowError |
Java's error when recursion goes too deep |
Summary
- A BST keeps smaller values left and bigger values right for the whole subtree, at every node; LeetCode forbids duplicates.
- Checking only the children is wrong (the trap tree). Checking every node against its subtree's max and min is correct but O(n · h): 22.8 s on the big tree.
- Passing a (low, high) range down with
longbounds checks each node once: O(n), 9 ms. Or check that the inorder sequence is strictly increasing. - Kth smallest: inorder is sorted, so count nodes with a shared, reset counter and stop at k: O(h + k).
- Bugs to remember:
intbounds, a counter passed by value, a counter never reset.
Next episode: Binary tree maximum path sum (hard).