Implement a Binary Search Tree in Java
Problem
A binary search tree (BST) is a tree where every node's left subtree holds smaller keys and its right subtree holds larger keys, so each comparison rules out one side.
Insert a set of keys into a BST, print them in sorted order, check whether two keys are present, and report the tree's height.
Java Program
import java.util.ArrayList;
import java.util.List;
public class BinarySearchTree {
static class Node {
int key;
Node left, right;
Node(int key) {
this.key = key;
}
}
private Node root;
void insert(int key) {
root = insert(root, key);
}
private Node insert(Node node, int key) {
if (node == null) return new Node(key); // found the empty spot
if (key < node.key) node.left = insert(node.left, key); // smaller keys go left
else if (key > node.key) node.right = insert(node.right, key); // larger keys go right
return node; // duplicates are ignored
}
boolean contains(int key) {
Node node = root;
while (node != null) {
if (key == node.key) return true;
node = key < node.key ? node.left : node.right; // discard one subtree each step
}
return false;
}
void inorder(Node node, List<Integer> out) { // left, node, right = ascending order
if (node == null) return;
inorder(node.left, out);
out.add(node.key);
inorder(node.right, out);
}
int height(Node node) {
return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
for (int key : new int[]{50, 30, 70, 20, 40, 60, 80, 35}) {
tree.insert(key);
}
List<Integer> sorted = new ArrayList<>();
tree.inorder(tree.root, sorted);
System.out.println("In-order: " + sorted);
System.out.println("Contains 40? " + tree.contains(40));
System.out.println("Contains 45? " + tree.contains(45));
System.out.println("Height: " + tree.height(tree.root));
}
}Output
Core Logic
Every operation follows the same rule from the root down: go left for a smaller key and right for a larger one, so the work depends on the tree's height rather than its size.
- 1
insertwalks down recursively and attaches a newNodeat the first empty spot it reaches; equal keys are ignored. - 2
containsuses a loop that discards one subtree at every step. - 3
inordervisits left subtree, node, then right subtree, which lists keys in ascending order. - 4
heightis one more than the taller of the two subtrees, with an empty tree counting as 0.
Key Point: Inserting already-sorted keys produces a lopsided tree that behaves like a linked list (O(n) per operation); self-balancing trees such as red-black trees — used by TreeMap — prevent this.
Why: Each operation follows one path from the root, of length h; the recursion stack is also h deep. For a balanced tree, h is about log n.
Key Concepts
Approach 2: Deleting a Node
import java.util.ArrayList;
import java.util.List;
public class BstDelete {
static class Node {
int key;
Node left, right;
Node(int key) {
this.key = key;
}
}
static Node insert(Node node, int key) {
if (node == null) return new Node(key);
if (key < node.key) node.left = insert(node.left, key);
else if (key > node.key) node.right = insert(node.right, key);
return node;
}
static Node delete(Node node, int key) {
if (node == null) return null;
if (key < node.key) {
node.left = delete(node.left, key);
} else if (key > node.key) {
node.right = delete(node.right, key);
} else {
if (node.left == null) return node.right; // no child or only a right child
if (node.right == null) return node.left; // only a left child
Node successor = node.right; // two children: smallest key on the right
while (successor.left != null) successor = successor.left;
node.key = successor.key; // copy it up
node.right = delete(node.right, successor.key); // then remove it from below
}
return node;
}
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 String show(Node root) {
List<Integer> out = new ArrayList<>();
inorder(root, out);
return out.toString();
}
public static void main(String[] args) {
Node root = null;
for (int key : new int[]{50, 30, 70, 20, 40, 60, 80, 35}) root = insert(root, key);
System.out.println("Start: " + show(root));
root = delete(root, 20); // a leaf
System.out.println("Delete 20 leaf: " + show(root));
root = delete(root, 40); // one child (35)
System.out.println("Delete 40: " + show(root));
root = delete(root, 50); // two children: replaced by its successor, 60
System.out.println("Delete 50 root: " + show(root) + ", new root " + root.key);
}
}
Output
Core Logic
Deletion has three cases: a leaf is simply removed, a node with one child is replaced by that child, and a node with two children takes its in-order successor's key.
- 1The search recurses left or right until it reaches the key.
- 2If one child is missing, the method returns the other child, which reconnects it to the parent.
- 3With two children, the smallest key in the right subtree (the successor) is copied into the node.
- 4That successor is then deleted from the right subtree, where it has at most one child.
Key Point: Using the in-order successor (or predecessor) keeps the BST ordering intact, because it's the closest larger key.
Why: Finding the node and its successor both follow a single root-to-leaf path.
Key Concepts
Interview Questions
How do you check whether a binary tree is a valid BST?
Pass an allowed range down the recursion: every left child must be smaller than its parent and every right child larger, all the way down — not just compared with its direct parent.
Which traversal gives the keys in sorted order?
In-order traversal (left, node, right).