A binary search tree keeps its keys ordered: everything in a node's left subtree is smaller, everything in its right subtree is larger. That one invariant is what every problem here exploits — the inorder traversal is sorted, every search is a single root-to-leaf walk, and a count stored in each node turns order statistics into O(h) queries.
20
/ \
8 22
/ \
4 12
/ \
10 14
inorder: 4 8 10 12 14 20 22 (always sorted)What the problems rely on
The reader already knows search, insert and delete. The advanced problems are built from four consequences of the BST invariant:
| Operation | Time | Note |
|---|---|---|
| search / insert / delete | O(h) | h = O(log n) when balanced, O(n) when skewed |
| floor / ceiling / successor | O(h) | one path down, remember the best candidate |
| kth smallest (plain) | O(h + k) | inorder traversal stopped after k nodes |
| kth smallest (augmented) | O(h) | each node stores the size of its left subtree |
| check if a tree is a BST | O(n) | range method or inorder-previous method |
| inorder traversal | O(n) | stack holds at most h nodes |
Floor and ceiling of a key
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def floor_of(root, x):
res = -1
while root:
if root.key == x:
return x
if root.key > x:
root = root.left # too big: only the left subtree can hold a floor
else:
res = root.key # candidate; a closer one may sit to the right
root = root.right
return res
def ceil_of(root, x):
res = -1
while root:
if root.key == x:
return x
if root.key < x:
root = root.right # too small: only the right subtree can hold a ceiling
else:
res = root.key # candidate; a closer one may sit to the left
root = root.left
return res
root = None
for k in [20, 8, 22, 4, 12, 10, 14]:
root = insert(root, k)
for x in [11, 23, 3, 12]:
print(f"x={x}: floor {floor_of(root, x)} ceiling {ceil_of(root, x)}")#include <iostream>
using namespace std;
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->key) root->left = insert(root->left, key);
else if (key > root->key) root->right = insert(root->right, key);
return root;
}
int floorOf(Node* root, int x) {
int res = -1;
while (root) {
if (root->key == x) return x;
if (root->key > x) root = root->left; // too big: go left
else { res = root->key; root = root->right; } // candidate, look right for a closer one
}
return res;
}
int ceilOf(Node* root, int x) {
int res = -1;
while (root) {
if (root->key == x) return x;
if (root->key < x) root = root->right; // too small: go right
else { res = root->key; root = root->left; } // candidate, look left for a closer one
}
return res;
}
int main() {
Node* root = nullptr;
for (int k : {20, 8, 22, 4, 12, 10, 14}) root = insert(root, k);
for (int x : {11, 23, 3, 12})
cout << "x=" << x << ": floor " << floorOf(root, x) << " ceiling " << ceilOf(root, x) << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
static int floorOf(Node root, int x) {
int res = -1;
while (root != null) {
if (root.key == x) return x;
if (root.key > x) root = root.left; // too big: go left
else { res = root.key; root = root.right; } // candidate, look right for a closer one
}
return res;
}
static int ceilOf(Node root, int x) {
int res = -1;
while (root != null) {
if (root.key == x) return x;
if (root.key < x) root = root.right; // too small: go right
else { res = root.key; root = root.left; } // candidate, look left for a closer one
}
return res;
}
public static void main(String[] args) {
Node root = null;
for (int k : new int[]{20, 8, 22, 4, 12, 10, 14}) root = insert(root, k);
for (int x : new int[]{11, 23, 3, 12})
System.out.println("x=" + x + ": floor " + floorOf(root, x) + " ceiling " + ceilOf(root, x));
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function insert(root, key) {
if (!root) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
function floorOf(root, x) {
let res = -1;
while (root) {
if (root.key === x) return x;
if (root.key > x) root = root.left; // too big: go left
else { res = root.key; root = root.right; } // candidate, look right for a closer one
}
return res;
}
function ceilOf(root, x) {
let res = -1;
while (root) {
if (root.key === x) return x;
if (root.key < x) root = root.right; // too small: go right
else { res = root.key; root = root.left; } // candidate, look left for a closer one
}
return res;
}
let root = null;
for (const k of [20, 8, 22, 4, 12, 10, 14]) root = insert(root, k);
for (const x of [11, 23, 3, 12])
console.log(`x=${x}: floor ${floorOf(root, x)} ceiling ${ceilOf(root, x)}`);x=11: floor 10 ceiling 12
x=23: floor 22 ceiling -1
x=3: floor -1 ceiling 4
x=12: floor 12 ceiling 12Time O(h) · Space O(1)
Ceiling on the left side of every element
For every arr[i], print the smallest element among arr[0..i-1] that is >= arr[i], or -1 if there is none. The first element never has one.
The obvious solution rescans the prefix for each element:
def left_ceilings_naive(arr):
res = [-1]
for i in range(1, len(arr)):
best = -1
for j in range(i): # scan everything to the left
if arr[j] >= arr[i] and (best == -1 or arr[j] < best):
best = arr[j]
res.append(best)
return res
print(*left_ceilings_naive([2, 8, 30, 15, 25, 12]))-1 -1 -1 30 30 15Time O(n²) · Space O(1)
from bisect import bisect_left, insort
def left_ceilings(arr):
seen = [] # kept sorted
res = []
for x in arr:
i = bisect_left(seen, x) # index of the first element >= x
res.append(seen[i] if i < len(seen) else -1)
insort(seen, x) # O(n) shift, but a tight memmove
return res
for arr in ([2, 8, 30, 15, 25, 12], [30, 20, 10]):
print(*left_ceilings(arr))#include <iostream>
#include <set>
#include <vector>
using namespace std;
vector<int> leftCeilings(const vector<int>& arr) {
set<int> seen; // red-black tree
vector<int> res;
for (int x : arr) {
auto it = seen.lower_bound(x); // first element >= x, O(log n)
res.push_back(it == seen.end() ? -1 : *it);
seen.insert(x);
}
return res;
}
int main() {
for (const vector<int>& arr : {vector<int>{2, 8, 30, 15, 25, 12}, vector<int>{30, 20, 10}}) {
vector<int> res = leftCeilings(arr);
for (int i = 0; i < (int)res.size(); i++) cout << (i ? " " : "") << res[i];
cout << "\n";
}
}import java.util.TreeSet;
public class Main {
static String leftCeilings(int[] arr) {
TreeSet<Integer> seen = new TreeSet<>(); // red-black tree
StringBuilder sb = new StringBuilder();
for (int x : arr) {
Integer c = seen.ceiling(x); // smallest element >= x, or null
sb.append(c == null ? -1 : c).append(' ');
seen.add(x);
}
return sb.toString().trim();
}
public static void main(String[] args) {
System.out.println(leftCeilings(new int[]{2, 8, 30, 15, 25, 12}));
System.out.println(leftCeilings(new int[]{30, 20, 10}));
}
}// JavaScript has no ordered set: reuse the BST insert + ceiling from above
class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function insert(root, key) {
if (!root) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
function ceilOf(root, x) {
let res = -1;
while (root) {
if (root.key === x) return x;
if (root.key < x) root = root.right;
else { res = root.key; root = root.left; }
}
return res;
}
function leftCeilings(arr) {
let seen = null;
const res = [];
for (const x of arr) {
res.push(ceilOf(seen, x)); // query the elements to the left
seen = insert(seen, x); // then add the current one
}
return res;
}
for (const arr of [[2, 8, 30, 15, 25, 12], [30, 20, 10]])
console.log(leftCeilings(arr).join(" "));-1 -1 -1 30 30 15
-1 30 20Time O(n log n) · Space O(n)
Kth smallest element
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def kth_smallest(root, k):
stack, node = [], root
while stack or node:
while node: # go as far left as possible
stack.append(node)
node = node.left
node = stack.pop() # the next key in sorted order
k -= 1
if k == 0:
return node.key
node = node.right
return -1 # fewer than k nodes
root = None
for x in [20, 8, 22, 4, 12, 10, 14]:
root = insert(root, x)
for k in (3, 7, 8):
print(f"k={k}: {kth_smallest(root, k)}")#include <iostream>
#include <stack>
using namespace std;
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->key) root->left = insert(root->left, key);
else if (key > root->key) root->right = insert(root->right, key);
return root;
}
int kthSmallest(Node* root, int k) {
stack<Node*> st;
Node* node = root;
while (!st.empty() || node) {
while (node) { st.push(node); node = node->left; } // go as far left as possible
node = st.top(); st.pop(); // next key in sorted order
if (--k == 0) return node->key;
node = node->right;
}
return -1; // fewer than k nodes
}
int main() {
Node* root = nullptr;
for (int x : {20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int k : {3, 7, 8}) cout << "k=" << k << ": " << kthSmallest(root, k) << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
static int kthSmallest(Node root, int k) {
Deque<Node> stack = new ArrayDeque<>();
Node node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; } // go as far left as possible
node = stack.pop(); // next key in sorted order
if (--k == 0) return node.key;
node = node.right;
}
return -1; // fewer than k nodes
}
public static void main(String[] args) {
Node root = null;
for (int x : new int[]{20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int k : new int[]{3, 7, 8}) System.out.println("k=" + k + ": " + kthSmallest(root, k));
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function insert(root, key) {
if (!root) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
function kthSmallest(root, k) {
const stack = [];
let node = root;
while (stack.length || node) {
while (node) { stack.push(node); node = node.left; } // go as far left as possible
node = stack.pop(); // next key in sorted order
if (--k === 0) return node.key;
node = node.right;
}
return -1; // fewer than k nodes
}
let root = null;
for (const x of [20, 8, 22, 4, 12, 10, 14]) root = insert(root, x);
for (const k of [3, 7, 8]) console.log(`k=${k}: ${kthSmallest(root, k)}`);k=3: 10
k=7: 22
k=8: -1Time O(h + k) · Space O(h)
When the tree is queried many times, or k is large, pay a little memory to make every query O(h): store in each node the number of nodes in its left subtree (lcount). Insert maintains it — every time the new key goes left, the node it passes gains one left descendant.
20 (lcount 5)
/ \
(lcount 1) 8 22 (0)
/ \
(0) 4 12 (lcount 1)
/ \
(0) 10 14 (0)
kth(k=3) at 20: lcount+1 = 6 > 3 → go left, k stays 3
at 8: lcount+1 = 2 < 3 → go right, k = 3-2 = 1
at 12: lcount+1 = 2 > 1 → go left
at 10: lcount+1 = 1 == 1 → answer 10class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.lcount = 0 # number of nodes in the left subtree
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
root.lcount += 1 # one more node went into my left subtree
elif key > root.key:
root.right = insert(root.right, key)
return root
def kth_smallest(root, k):
while root:
rank = root.lcount + 1 # this node is the rank-th smallest of its subtree
if rank == k:
return root.key
if k < rank:
root = root.left # answer is in the left subtree
else:
k -= rank # skip the left subtree and this node
root = root.right
return -1
root = None
for x in [20, 8, 22, 4, 12, 10, 14]:
root = insert(root, x)
for k in (3, 7, 8):
print(f"k={k}: {kth_smallest(root, k)}")#include <iostream>
using namespace std;
struct Node {
int key;
int lcount = 0; // number of nodes in the left subtree
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->key) {
root->left = insert(root->left, key);
root->lcount++; // one more node went into my left subtree
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
int kthSmallest(Node* root, int k) {
while (root) {
int rank = root->lcount + 1; // this node is the rank-th smallest of its subtree
if (rank == k) return root->key;
if (k < rank) root = root->left; // answer is in the left subtree
else { k -= rank; root = root->right; } // skip the left subtree and this node
}
return -1;
}
int main() {
Node* root = nullptr;
for (int x : {20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int k : {3, 7, 8}) cout << "k=" << k << ": " << kthSmallest(root, k) << "\n";
}public class Main {
static class Node {
int key, lcount; // lcount = number of nodes in the left subtree
Node left, right;
Node(int k) { key = k; }
}
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) {
root.left = insert(root.left, key);
root.lcount++; // one more node went into my left subtree
} else if (key > root.key) {
root.right = insert(root.right, key);
}
return root;
}
static int kthSmallest(Node root, int k) {
while (root != null) {
int rank = root.lcount + 1; // this node is the rank-th smallest of its subtree
if (rank == k) return root.key;
if (k < rank) root = root.left; // answer is in the left subtree
else { k -= rank; root = root.right; } // skip the left subtree and this node
}
return -1;
}
public static void main(String[] args) {
Node root = null;
for (int x : new int[]{20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int k : new int[]{3, 7, 8}) System.out.println("k=" + k + ": " + kthSmallest(root, k));
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; this.lcount = 0; }
}
function insert(root, key) {
if (!root) return new Node(key);
if (key < root.key) {
root.left = insert(root.left, key);
root.lcount++; // one more node went into my left subtree
} else if (key > root.key) {
root.right = insert(root.right, key);
}
return root;
}
function kthSmallest(root, k) {
while (root) {
const rank = root.lcount + 1; // this node is the rank-th smallest of its subtree
if (rank === k) return root.key;
if (k < rank) root = root.left; // answer is in the left subtree
else { k -= rank; root = root.right; } // skip the left subtree and this node
}
return -1;
}
let root = null;
for (const x of [20, 8, 22, 4, 12, 10, 14]) root = insert(root, x);
for (const k of [3, 7, 8]) console.log(`k=${k}: ${kthSmallest(root, k)}`);k=3: 10
k=7: 22
k=8: -1Time O(h) · Space O(1)
Check whether a binary tree is a BST
tree A (valid) tree B (NOT a BST)
20 20
/ \ / \
8 22 8 22
/ \ / \
4 12 4 25 ← 25 > 20 but sits in 20's left subtree
/ \
10 14The tempting solution compares each node with its two children only. It accepts tree B:
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def looks_like_bst(root): # WRONG: only compares a node with its own children
if root is None:
return True
if root.left and root.left.key > root.key:
return False
if root.right and root.right.key < root.key:
return False
return looks_like_bst(root.left) and looks_like_bst(root.right)
b = Node(20)
b.left, b.right = Node(8), Node(22)
b.left.left, b.left.right = Node(4), Node(25) # 25 violates the rule at its grandparent 20
print("tree B:", "Yes" if looks_like_bst(b) else "No")tree B: YesA correct but slow fix checks, for every node, the maximum of the whole left subtree and the minimum of the whole right subtree. Each node is scanned by each of its ancestors, which is O(n²) on a skewed tree:
import sys
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def max_key(root):
if root is None:
return -sys.maxsize
return max(root.key, max_key(root.left), max_key(root.right))
def min_key(root):
if root is None:
return sys.maxsize
return min(root.key, min_key(root.left), min_key(root.right))
def is_bst_slow(root):
if root is None:
return True
if root.left and max_key(root.left) >= root.key: # whole left subtree must be smaller
return False
if root.right and min_key(root.right) <= root.key: # whole right subtree must be larger
return False
return is_bst_slow(root.left) and is_bst_slow(root.right)
a = Node(20)
a.left, a.right = Node(8), Node(22)
a.left.left, a.left.right = Node(4), Node(12)
a.left.right.left, a.left.right.right = Node(10), Node(14)
b = Node(20)
b.left, b.right = Node(8), Node(22)
b.left.left, b.left.right = Node(4), Node(25)
print("tree A:", "Yes" if is_bst_slow(a) else "No")
print("tree B:", "Yes" if is_bst_slow(b) else "No")tree A: Yes
tree B: NoTime O(n²) worst case · Space O(h)
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def is_bst(root, lo=float("-inf"), hi=float("inf")):
if root is None:
return True
if not (lo < root.key < hi): # must lie strictly inside the ancestors' range
return False
return (is_bst(root.left, lo, root.key) # left subtree: everything < root.key
and is_bst(root.right, root.key, hi)) # right subtree: everything > root.key
a = Node(20)
a.left, a.right = Node(8), Node(22)
a.left.left, a.left.right = Node(4), Node(12)
a.left.right.left, a.left.right.right = Node(10), Node(14)
b = Node(20)
b.left, b.right = Node(8), Node(22)
b.left.left, b.left.right = Node(4), Node(25)
print("tree A:", "Yes" if is_bst(a) else "No")
print("tree B:", "Yes" if is_bst(b) else "No")#include <climits>
#include <iostream>
using namespace std;
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
bool isBST(Node* root, long long lo, long long hi) {
if (!root) return true;
if (root->key <= lo || root->key >= hi) return false; // outside the ancestors' range
return isBST(root->left, lo, root->key) // left: everything < key
&& isBST(root->right, root->key, hi); // right: everything > key
}
int main() {
Node* a = new Node(20);
a->left = new Node(8); a->right = new Node(22);
a->left->left = new Node(4); a->left->right = new Node(12);
a->left->right->left = new Node(10); a->left->right->right = new Node(14);
Node* b = new Node(20);
b->left = new Node(8); b->right = new Node(22);
b->left->left = new Node(4); b->left->right = new Node(25);
cout << "tree A: " << (isBST(a, LLONG_MIN, LLONG_MAX) ? "Yes" : "No") << "\n";
cout << "tree B: " << (isBST(b, LLONG_MIN, LLONG_MAX) ? "Yes" : "No") << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static boolean isBST(Node root, long lo, long hi) {
if (root == null) return true;
if (root.key <= lo || root.key >= hi) return false; // outside the ancestors' range
return isBST(root.left, lo, root.key) // left: everything < key
&& isBST(root.right, root.key, hi); // right: everything > key
}
public static void main(String[] args) {
Node a = new Node(20);
a.left = new Node(8); a.right = new Node(22);
a.left.left = new Node(4); a.left.right = new Node(12);
a.left.right.left = new Node(10); a.left.right.right = new Node(14);
Node b = new Node(20);
b.left = new Node(8); b.right = new Node(22);
b.left.left = new Node(4); b.left.right = new Node(25);
System.out.println("tree A: " + (isBST(a, Long.MIN_VALUE, Long.MAX_VALUE) ? "Yes" : "No"));
System.out.println("tree B: " + (isBST(b, Long.MIN_VALUE, Long.MAX_VALUE) ? "Yes" : "No"));
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function isBST(root, lo = -Infinity, hi = Infinity) {
if (!root) return true;
if (root.key <= lo || root.key >= hi) return false; // outside the ancestors' range
return isBST(root.left, lo, root.key) // left: everything < key
&& isBST(root.right, root.key, hi); // right: everything > key
}
const a = new Node(20);
a.left = new Node(8); a.right = new Node(22);
a.left.left = new Node(4); a.left.right = new Node(12);
a.left.right.left = new Node(10); a.left.right.right = new Node(14);
const b = new Node(20);
b.left = new Node(8); b.right = new Node(22);
b.left.left = new Node(4); b.left.right = new Node(25);
console.log("tree A:", isBST(a) ? "Yes" : "No");
console.log("tree B:", isBST(b) ? "Yes" : "No");tree A: Yes
tree B: NoTime O(n) · Space O(h)
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def is_bst(root):
stack, node, prev = [], root, None
while stack or node:
while node: # iterative inorder traversal
stack.append(node)
node = node.left
node = stack.pop()
if prev is not None and node.key <= prev: # inorder must strictly increase
return False
prev = node.key
node = node.right
return True
a = Node(20)
a.left, a.right = Node(8), Node(22)
a.left.left, a.left.right = Node(4), Node(12)
a.left.right.left, a.left.right.right = Node(10), Node(14)
b = Node(20)
b.left, b.right = Node(8), Node(22)
b.left.left, b.left.right = Node(4), Node(25)
print("tree A:", "Yes" if is_bst(a) else "No")
print("tree B:", "Yes" if is_bst(b) else "No")#include <iostream>
#include <stack>
using namespace std;
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
bool isBST(Node* root) {
stack<Node*> st;
Node* node = root;
bool havePrev = false;
int prev = 0;
while (!st.empty() || node) {
while (node) { st.push(node); node = node->left; } // iterative inorder traversal
node = st.top(); st.pop();
if (havePrev && node->key <= prev) return false; // inorder must strictly increase
prev = node->key; havePrev = true;
node = node->right;
}
return true;
}
int main() {
Node* a = new Node(20);
a->left = new Node(8); a->right = new Node(22);
a->left->left = new Node(4); a->left->right = new Node(12);
a->left->right->left = new Node(10); a->left->right->right = new Node(14);
Node* b = new Node(20);
b->left = new Node(8); b->right = new Node(22);
b->left->left = new Node(4); b->left->right = new Node(25);
cout << "tree A: " << (isBST(a) ? "Yes" : "No") << "\n";
cout << "tree B: " << (isBST(b) ? "Yes" : "No") << "\n";
}import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static boolean isBST(Node root) {
Deque<Node> stack = new ArrayDeque<>();
Node node = root;
Integer prev = null;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; } // iterative inorder
node = stack.pop();
if (prev != null && node.key <= prev) return false; // must strictly increase
prev = node.key;
node = node.right;
}
return true;
}
public static void main(String[] args) {
Node a = new Node(20);
a.left = new Node(8); a.right = new Node(22);
a.left.left = new Node(4); a.left.right = new Node(12);
a.left.right.left = new Node(10); a.left.right.right = new Node(14);
Node b = new Node(20);
b.left = new Node(8); b.right = new Node(22);
b.left.left = new Node(4); b.left.right = new Node(25);
System.out.println("tree A: " + (isBST(a) ? "Yes" : "No"));
System.out.println("tree B: " + (isBST(b) ? "Yes" : "No"));
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function isBST(root) {
const stack = [];
let node = root, prev = null;
while (stack.length || node) {
while (node) { stack.push(node); node = node.left; } // iterative inorder traversal
node = stack.pop();
if (prev !== null && node.key <= prev) return false; // inorder must strictly increase
prev = node.key;
node = node.right;
}
return true;
}
const a = new Node(20);
a.left = new Node(8); a.right = new Node(22);
a.left.left = new Node(4); a.left.right = new Node(12);
a.left.right.left = new Node(10); a.left.right.right = new Node(14);
const b = new Node(20);
b.left = new Node(8); b.right = new Node(22);
b.left.left = new Node(4); b.left.right = new Node(25);
console.log("tree A:", isBST(a) ? "Yes" : "No");
console.log("tree B:", isBST(b) ? "Yes" : "No");tree A: Yes
tree B: NoTime O(n) · Space O(h)
Fix a BST with two nodes swapped
given (two keys swapped) fixed
20 20
/ \ / \
60 80 ──▶ 8 80
/ \ / \ / \ / \
4 10 8 100 4 10 60 100
inorder: 4 60 10 20 8 80 100 → 4 8 10 20 60 80 100
^^^^^^ ^^^^^
dip 1 dip 2Traverse inorder, remembering
prevAt each node compare
node.keywithprev.key.First dip (
node.key < prev.key)Set
first = prevandsecond = node.Second dip
Only
second = nodechanges —firststays the larger element of the first dip.Swap
Exchange
first.keyandsecond.key. The structure of the tree is untouched.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class Fixer:
def __init__(self):
self.prev = self.first = self.second = None
def visit(self, node): # inorder, looking for dips
if node is None:
return
self.visit(node.left)
if self.prev and node.key < self.prev.key: # a dip: smaller key after a larger one
if self.first is None:
self.first = self.prev # first dip: remember the larger element
self.second = node # the smaller element (overwritten by a 2nd dip)
self.prev = node
self.visit(node.right)
def fix_bst(root):
f = Fixer()
f.visit(root)
if f.first and f.second:
f.first.key, f.second.key = f.second.key, f.first.key
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.key)
inorder(node.right, out)
root = Node(20)
root.left, root.right = Node(60), Node(80)
root.left.left, root.left.right = Node(4), Node(10)
root.right.left, root.right.right = Node(8), Node(100)
before = []
inorder(root, before)
print("before:", *before)
fix_bst(root)
after = []
inorder(root, after)
print("after:", *after)#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
struct Fixer {
Node *prev = nullptr, *first = nullptr, *second = nullptr;
void visit(Node* node) { // inorder, looking for dips
if (!node) return;
visit(node->left);
if (prev && node->key < prev->key) { // a dip: smaller key after a larger one
if (!first) first = prev; // first dip: remember the larger element
second = node; // the smaller element (overwritten by a 2nd dip)
}
prev = node;
visit(node->right);
}
};
void fixBST(Node* root) {
Fixer f;
f.visit(root);
if (f.first && f.second) swap(f.first->key, f.second->key);
}
void inorder(Node* node, vector<int>& out) {
if (!node) return;
inorder(node->left, out);
out.push_back(node->key);
inorder(node->right, out);
}
void printKeys(const char* label, Node* root) {
vector<int> keys;
inorder(root, keys);
cout << label;
for (int k : keys) cout << " " << k;
cout << "\n";
}
int main() {
Node* root = new Node(20);
root->left = new Node(60); root->right = new Node(80);
root->left->left = new Node(4); root->left->right = new Node(10);
root->right->left = new Node(8); root->right->right = new Node(100);
printKeys("before:", root);
fixBST(root);
printKeys("after:", root);
}import java.util.ArrayList;
import java.util.List;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static class Fixer {
Node prev, first, second;
void visit(Node node) { // inorder, looking for dips
if (node == null) return;
visit(node.left);
if (prev != null && node.key < prev.key) { // a dip: smaller key after a larger one
if (first == null) first = prev; // first dip: remember the larger element
second = node; // the smaller element (overwritten by a 2nd dip)
}
prev = node;
visit(node.right);
}
}
static void fixBST(Node root) {
Fixer f = new Fixer();
f.visit(root);
if (f.first != null && f.second != null) {
int t = f.first.key; f.first.key = f.second.key; f.second.key = t;
}
}
static void inorder(Node node, List<Integer> out) {
if (node == null) return;
inorder(node.left, out);
out.add(node.key);
inorder(node.right, out);
}
static void printKeys(String label, Node root) {
List<Integer> keys = new ArrayList<>();
inorder(root, keys);
StringBuilder sb = new StringBuilder(label);
for (int k : keys) sb.append(' ').append(k);
System.out.println(sb);
}
public static void main(String[] args) {
Node root = new Node(20);
root.left = new Node(60); root.right = new Node(80);
root.left.left = new Node(4); root.left.right = new Node(10);
root.right.left = new Node(8); root.right.right = new Node(100);
printKeys("before:", root);
fixBST(root);
printKeys("after:", root);
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class Fixer {
constructor() { this.prev = null; this.first = null; this.second = null; }
visit(node) { // inorder, looking for dips
if (!node) return;
this.visit(node.left);
if (this.prev && node.key < this.prev.key) { // a dip: smaller key after a larger one
if (!this.first) this.first = this.prev; // first dip: remember the larger element
this.second = node; // the smaller element (overwritten by a 2nd dip)
}
this.prev = node;
this.visit(node.right);
}
}
function fixBST(root) {
const f = new Fixer();
f.visit(root);
if (f.first && f.second) [f.first.key, f.second.key] = [f.second.key, f.first.key];
}
function inorder(node, out) {
if (!node) return;
inorder(node.left, out);
out.push(node.key);
inorder(node.right, out);
}
const root = new Node(20);
root.left = new Node(60); root.right = new Node(80);
root.left.left = new Node(4); root.left.right = new Node(10);
root.right.left = new Node(8); root.right.right = new Node(100);
const before = [];
inorder(root, before);
console.log("before:", before.join(" "));
fixBST(root);
const after = [];
inorder(root, after);
console.log("after:", after.join(" "));before: 4 60 10 20 8 80 100
after: 4 8 10 20 60 80 100Time O(n) · Space O(h)
Pair with a given sum in a BST
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.key)
inorder(node.right, out)
def pair_sum(root, target):
keys = []
inorder(root, keys) # sorted keys
i, j = 0, len(keys) - 1
while i < j: # two pointers on a sorted array
s = keys[i] + keys[j]
if s == target:
return (keys[i], keys[j])
if s < target:
i += 1 # need a bigger sum
else:
j -= 1 # need a smaller sum
return None
root = None
for x in [20, 8, 22, 4, 12, 10, 14]:
root = insert(root, x)
for target in (30, 29):
res = pair_sum(root, target)
print(f"sum={target}:", f"Yes ({res[0]} + {res[1]})" if res else "No")#include <iostream>
#include <vector>
using namespace std;
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->key) root->left = insert(root->left, key);
else if (key > root->key) root->right = insert(root->right, key);
return root;
}
void inorder(Node* node, vector<int>& out) {
if (!node) return;
inorder(node->left, out);
out.push_back(node->key);
inorder(node->right, out);
}
bool pairSum(Node* root, int target, int& a, int& b) {
vector<int> keys;
inorder(root, keys); // sorted keys
int i = 0, j = (int)keys.size() - 1;
while (i < j) { // two pointers on a sorted array
int s = keys[i] + keys[j];
if (s == target) { a = keys[i]; b = keys[j]; return true; }
if (s < target) i++; // need a bigger sum
else j--; // need a smaller sum
}
return false;
}
int main() {
Node* root = nullptr;
for (int x : {20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int target : {30, 29}) {
int a, b;
if (pairSum(root, target, a, b)) cout << "sum=" << target << ": Yes (" << a << " + " << b << ")\n";
else cout << "sum=" << target << ": No\n";
}
}import java.util.ArrayList;
import java.util.List;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
static void inorder(Node node, List<Integer> out) {
if (node == null) return;
inorder(node.left, out);
out.add(node.key);
inorder(node.right, out);
}
static int[] pairSum(Node root, int target) {
List<Integer> keys = new ArrayList<>();
inorder(root, keys); // sorted keys
int i = 0, j = keys.size() - 1;
while (i < j) { // two pointers on a sorted array
int s = keys.get(i) + keys.get(j);
if (s == target) return new int[]{keys.get(i), keys.get(j)};
if (s < target) i++; // need a bigger sum
else j--; // need a smaller sum
}
return null;
}
public static void main(String[] args) {
Node root = null;
for (int x : new int[]{20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int target : new int[]{30, 29}) {
int[] res = pairSum(root, target);
System.out.println("sum=" + target + ": " + (res == null ? "No" : "Yes (" + res[0] + " + " + res[1] + ")"));
}
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function insert(root, key) {
if (!root) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
function inorder(node, out) {
if (!node) return;
inorder(node.left, out);
out.push(node.key);
inorder(node.right, out);
}
function pairSum(root, target) {
const keys = [];
inorder(root, keys); // sorted keys
let i = 0, j = keys.length - 1;
while (i < j) { // two pointers on a sorted array
const s = keys[i] + keys[j];
if (s === target) return [keys[i], keys[j]];
if (s < target) i++; // need a bigger sum
else j--; // need a smaller sum
}
return null;
}
let root = null;
for (const x of [20, 8, 22, 4, 12, 10, 14]) root = insert(root, x);
for (const target of [30, 29]) {
const res = pairSum(root, target);
console.log(`sum=${target}:`, res ? `Yes (${res[0]} + ${res[1]})` : "No");
}sum=30: Yes (8 + 22)
sum=29: NoTime O(n) · Space O(n)
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def pair_sum(node, target, seen):
if node is None:
return None
found = pair_sum(node.left, target, seen)
if found:
return found
if target - node.key in seen: # the partner was visited earlier
return (target - node.key, node.key)
seen.add(node.key)
return pair_sum(node.right, target, seen)
root = None
for x in [20, 8, 22, 4, 12, 10, 14]:
root = insert(root, x)
for target in (30, 29):
res = pair_sum(root, target, set()) # a fresh set per query
print(f"sum={target}:", f"Yes ({res[0]} + {res[1]})" if res else "No")#include <iostream>
#include <unordered_set>
using namespace std;
struct Node {
int key;
Node *left = nullptr, *right = nullptr;
Node(int k) : key(k) {}
};
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->key) root->left = insert(root->left, key);
else if (key > root->key) root->right = insert(root->right, key);
return root;
}
bool pairSum(Node* node, int target, unordered_set<int>& seen, int& a, int& b) {
if (!node) return false;
if (pairSum(node->left, target, seen, a, b)) return true;
if (seen.count(target - node->key)) { // the partner was visited earlier
a = target - node->key; b = node->key;
return true;
}
seen.insert(node->key);
return pairSum(node->right, target, seen, a, b);
}
int main() {
Node* root = nullptr;
for (int x : {20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int target : {30, 29}) {
unordered_set<int> seen; // a fresh set per query
int a, b;
if (pairSum(root, target, seen, a, b)) cout << "sum=" << target << ": Yes (" << a << " + " << b << ")\n";
else cout << "sum=" << target << ": No\n";
}
}import java.util.HashSet;
import java.util.Set;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
static int[] pairSum(Node node, int target, Set<Integer> seen) {
if (node == null) return null;
int[] found = pairSum(node.left, target, seen);
if (found != null) return found;
if (seen.contains(target - node.key)) // the partner was visited earlier
return new int[]{target - node.key, node.key};
seen.add(node.key);
return pairSum(node.right, target, seen);
}
public static void main(String[] args) {
Node root = null;
for (int x : new int[]{20, 8, 22, 4, 12, 10, 14}) root = insert(root, x);
for (int target : new int[]{30, 29}) {
int[] res = pairSum(root, target, new HashSet<>()); // a fresh set per query
System.out.println("sum=" + target + ": " + (res == null ? "No" : "Yes (" + res[0] + " + " + res[1] + ")"));
}
}
}class Node {
constructor(key) { this.key = key; this.left = null; this.right = null; }
}
function insert(root, key) {
if (!root) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
function pairSum(node, target, seen) {
if (!node) return null;
const found = pairSum(node.left, target, seen);
if (found) return found;
if (seen.has(target - node.key)) // the partner was visited earlier
return [target - node.key, node.key];
seen.add(node.key);
return pairSum(node.right, target, seen);
}
let root = null;
for (const x of [20, 8, 22, 4, 12, 10, 14]) root = insert(root, x);
for (const target of [30, 29]) {
const res = pairSum(root, target, new Set()); // a fresh set per query
console.log(`sum=${target}:`, res ? `Yes (${res[0]} + ${res[1]})` : "No");
}sum=30: Yes (10 + 20)
sum=29: NoTime O(n) · Space O(n)
Interview Q&A
Why is the inorder traversal of a BST sorted?
How do you find the kth smallest in O(h) when the tree changes over time?
Why does comparing a node with its children not prove a tree is a BST?
Two nodes of a BST were swapped. How many dips can the inorder sequence have, and which nodes do you swap back?
What are std::set, TreeMap and heapq in terms of BSTs?
How would you find the lowest common ancestor of two keys in a BST?