Definition
- Binary Search Tree (BST) – a binary tree that maintains an ordering invariant: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.
- Logarithmic search – each comparison eliminates half the remaining tree, giving O(log n) search when the tree is balanced.
- Inorder traversal – visiting left, node, right produces values in sorted ascending order.
- Self-balancing – AVL and Red-Black trees keep the height logarithmic, preventing degeneration to a linked list.
- Java standard library – TreeMap and TreeSet are Red-Black BSTs providing sorted iteration and O(log n) operations.
Imagine the National Bank of India arranges account balances on a special noticeboard shaped like a tree. Every balance smaller than the one in your hand hangs on the left branch, and every larger balance hangs on the right. To find a particular balance you start at the top and at each step go left if smaller or right if larger. You never look at the whole board: you eliminate half the possibilities at every step.
Understanding the Concepts
What is a Binary Search Tree?
A binary search tree is a binary tree where every node obeys the ordering invariant: all values in the left subtree are strictly less than the node's value, and all values in the right subtree are strictly greater. This invariant enables search by comparison rather than by scanning.
package com.bank.service;
import java.math.BigDecimal;
public class BSTNode {
BigDecimal balance;
BSTNode left, right;
BSTNode(BigDecimal balance) {
this.balance = balance;
}
}
How does search work in a BST?
You start at the root and compare the target with the node's value. If the target is smaller, go left. If the target is larger, go right. If they are equal, you found it. Each comparison discards half the remaining tree in a balanced BST.
package com.bank.service;
import java.math.BigDecimal;
public class BSTSearch {
public static BSTNode search(BSTNode root, BigDecimal target) {
BSTNode current = root;
while (current != null) {
int cmp = target.compareTo(current.balance);
if (cmp < 0) current = current.left;
else if (cmp > 0) current = current.right;
else return current; // found
}
return null; // not found
}
}
How does insert work?
Insert follows the same comparison path until it finds an empty spot (a null child pointer) and links the new node there.
package com.bank.service;
import java.math.BigDecimal;
public class BSTInsert {
public static BSTNode insert(BSTNode root, BigDecimal value) {
if (root == null) return new BSTNode(value);
int cmp = value.compareTo(root.balance);
if (cmp < 0) root.left = insert(root.left, value);
else if (cmp > 0) root.right = insert(root.right, value);
// cmp == 0: duplicate, no insert (or update existing)
return root;
}
public static void main(String[] args) {
BSTNode root = null;
BigDecimal[] balances = {
new BigDecimal("50000"), new BigDecimal("30000"),
new BigDecimal("70000"), new BigDecimal("20000")
};
for (BigDecimal b : balances) root = insert(root, b);
System.out.println("Root balance: " + root.balance);
}
}
Root balance: 50000
How does delete work?
- Delete is the trickiest BST operation. There are three cases:
- The node is a leaf: simply remove it.
- The node has one child: replace the node with its child.
- The node has two children: replace the node's value with its inorder successor (smallest in the right subtree), then delete the successor.
package com.bank.service;
import java.math.BigDecimal;
public class BSTDelete {
public static BSTNode delete(BSTNode root, BigDecimal target) {
if (root == null) return null;
int cmp = target.compareTo(root.balance);
if (cmp < 0) {
root.left = delete(root.left, target);
} else if (cmp > 0) {
root.right = delete(root.right, target);
} else {
// Found the node to delete
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// Two children: find inorder successor
BSTNode successor = findMin(root.right);
root.balance = successor.balance;
root.right = delete(root.right, successor.balance);
}
return root;
}
private static BSTNode findMin(BSTNode node) {
while (node.left != null) node = node.left;
return node;
}
}
Why does inorder traversal produce sorted output?
By definition, all left-subtree values are smaller and all right-subtree values are larger. Visiting left first, then the node, then right, naturally produces ascending order.
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
public class BSTInorder {
public static List<BigDecimal> inorder(BSTNode root) {
List<BigDecimal> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private static void inorderHelper(BSTNode node, List<BigDecimal> result) {
if (node == null) return;
inorderHelper(node.left, result);
result.add(node.balance);
inorderHelper(node.right, result);
}
public static void main(String[] args) {
BSTNode root = null;
for (BigDecimal b : new BigDecimal[]{new BigDecimal("50000"),
new BigDecimal("30000"), new BigDecimal("70000"),
new BigDecimal("20000"), new BigDecimal("40000")}) {
root = BSTInsert.insert(root, b);
}
System.out.println("Sorted balances: " + inorder(root));
}
}
Sorted balances: [20000, 30000, 40000, 50000, 70000]
What happens when a BST degenerates?
If you insert already-sorted data into a naive BST, it degenerates into a straight line (effectively a linked list). Search drops from O(log n) to O(n).
// Inserting sorted values: 10000, 20000, 30000, 40000, 50000
// BST becomes:
// 10000
// \
// 20000
// \
// 30000
// \
// 40000
// \
// 50000
// Height = n - 1, search = O(n)
How do self-balancing trees fix this?
Self-balancing BSTs like AVL trees and Red-Black trees automatically rotate nodes after inserts and deletes to keep the height logarithmic. Java's TreeMap and TreeSet use Red-Black trees.
package com.bank.service;
import java.math.BigDecimal;
import java.util.TreeMap;
public class BalancedBSTDemo {
public static void main(String[] args) {
TreeMap<BigDecimal, String> accountsByBalance = new TreeMap<>();
accountsByBalance.put(new BigDecimal("50000"), "Rajesh");
accountsByBalance.put(new BigDecimal("30000"), "Priya");
accountsByBalance.put(new BigDecimal("70000"), "Pankaj");
// Range query: balances between 25000 and 60000
System.out.println("In range: " +
accountsByBalance.subMap(new BigDecimal("25000"), new BigDecimal("60000")));
// Sorted iteration
System.out.println("All sorted: " + accountsByBalance);
}
}
In range: {30000=Priya, 50000=Rajesh}
All sorted: {30000=Priya, 50000=Rajesh, 70000=Pankaj}
What are common mistakes?
The most common mistake in BST problems is not using compareTo for custom types, especially BigDecimal, and accidentally using == which compares object references.
// WRONG: comparing BigDecimal with ==
if (target == node.balance) { ... } // compares references, not values
// CORRECT: using compareTo
if (target.compareTo(node.balance) == 0) { ... } // compares numeric values
When should you use a BST in production?
In production, use Java's TreeMap or TreeSet rather than a hand-rolled BST, because they are self-balancing Red-Black trees with guaranteed O(log n) operations and sorted iteration. Use them when you need an ordered map or ordered set, range queries, or floor/ceiling operations.
package com.bank.service;
import java.math.BigDecimal;
import java.util.TreeMap;
public class InterestTierLookup {
public static void main(String[] args) {
TreeMap<BigDecimal, BigDecimal> tiers = new TreeMap<>();
tiers.put(new BigDecimal("0"), new BigDecimal("3.5"));
tiers.put(new BigDecimal("100000"), new BigDecimal("4.0"));
tiers.put(new BigDecimal("500000"), new BigDecimal("4.5"));
BigDecimal balance = new BigDecimal("250000");
BigDecimal rate = tiers.floorEntry(balance).getValue();
System.out.println("Rate for " + balance + ": " + rate + "%");
}
}
Rate for 250000: 4.0%
What should a senior engineer know?
A senior engineer should understand the difference between AVL and Red-Black trees: AVL enforces strict height balance (at most 1 height difference between siblings) giving slightly faster lookups but more rotations on insert/delete, while Red-Black trees allow approximate balance with fewer rotations, making them better for write-heavy workloads. Java chose Red-Black for TreeMap.
The BST invariant also underlies the validation problem: check whether a binary tree is a valid BST by passing min/max bounds down the recursion.
What are common interview follow-up questions?
- Interviewers commonly ask:
- How do you validate a BST? (Inorder traversal must be sorted, or pass min/max bounds.)
- What is the time complexity of BST operations? (O(h) where h is height; O(log n) if balanced.)
- AVL vs Red-Black? (AVL: stricter balance, faster lookups, more rotations. Red-Black: approximate balance, fewer rotations.)
- How does TreeMap implement floor/ceiling? (BST search to the closest node in O(log n).)
Visual Overview
BST with account balances:
50000
/ \
30000 70000
/ \
20000 40000
Search for 40000:
50000 → 40000 < 50000 → go left
30000 → 40000 > 30000 → go right
40000 → found! (3 comparisons)
Inorder traversal:
20000 → 30000 → 40000 → 50000 → 70000
(sorted ascending)
Degenerate BST (sorted inserts):
10000
\
20000
\
30000
\
40000 → linked list, O(n) search
Key Takeaway
A binary search tree maintains the ordering invariant that for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That single invariant makes searching fast: at each node you compare your target with the node's value and move left or right, discarding half the remaining tree on every step. In a balanced tree this gives O(log n) search, insert, and delete.
Inorder traversal of a BST visits values in sorted ascending order, which makes it a natural ordered map or ordered set. In the banking context, this means you can iterate account balances in sorted order and perform range queries like finding all balances between two amounts.
The danger is degeneration. If you insert sorted data into a naive BST, it becomes a linked list and operations fall back to O(n). Self-balancing trees like AVL and Red-Black fix this by rotating nodes to keep the height logarithmic. In production, use Java's TreeMap and TreeSet, which are Red-Black BSTs with guaranteed O(log n) operations.
At the National Bank of India, Rajesh uses TreeMap to look up interest-rate tiers by balance. The floorEntry method finds the correct tier in O(log n), and sorted iteration lets the report list all tiers in ascending balance order without a separate sort.
Remember one sentence: a BST keeps smaller values left and larger values right, so each comparison halves the search space, and self-balancing variants guarantee that halving always works.
---