A tree data structure organizes values through parent and child relationships. A binary search tree in Java, usually shortened to BST, gives each node at most two children and keeps smaller keys on its left and larger keys on its right. That ordering lets a search discard an entire subtree after each comparison.
This lesson builds a small catalogue of numbered lockers. The numbers are keys, rather than positions in an array. You will insert a number, find it, and print the catalogue in increasing order. Basic classes, references and recursion are the prerequisites.
Nodes, roots, leaves and height
A node stores a key and references to children. The root is the entry point to the tree. A leaf has no children. A subtree consists of a node and everything reachable below it. An empty child reference means that branch has no node; it does not mean a locker numbered zero exists.
A binary tree describes shape: each node has at most two children. A binary search tree adds an ordering rule. Every key in a node's left subtree must be smaller than that node's key, not merely its immediate left child's key. The corresponding right subtree must contain larger keys.
Suppose the root is 40, its left child is 20, and 20 has a right child of 50. Each parent appears to have an appropriately positioned child locally, but 50 violates the root's rule. It belongs in the right subtree of 40.
Height measures the longest route down the tree. Some references count edges and others count nodes, so state your convention when comparing results. Our search cost depends on how many nodes that route visits, whichever height convention you choose.
Choosing a duplicate policy
Ignoring duplicates is appropriate for a set of locker numbers. A stock catalogue might instead store a quantity beside each key and increment it when another item arrives. A map-like tree might replace the value associated with an existing key.
Choose the policy before writing insertion. Allowing equal keys on an arbitrary side without documenting that decision makes search, deletion and validation harder to reason about. Our strict smaller-or-larger rule keeps the teaching example simple.
The insertion method returns a subtree root because a previously empty subtree becomes a new node. Forgetting node.left = insert(...) loses that connection. Creating a node inside the recursive call is insufficient if its parent never receives the returned reference.
Traversal orders answer different questions
In-order traversal is useful when you want sorted keys from a valid BST. Pre-order visits the current node before its children and can help describe a tree's structure. Post-order visits children before their parent, which is useful when a parent calculation depends on child results.
Traversal is different from searching. Printing every key necessarily visits all n nodes and takes O(n) time. Recursive traversal also consumes stack space proportional to height. A badly skewed tree can make this stack large enough to overflow.
A level-order traversal visits nodes by depth and normally uses a queue. It can expose an unbalanced shape that sorted output hides. Two trees can print the same in-order sequence while having very different heights.
Complexity and production alternatives
Insertion and search take O(h) time, where h describes the tree's height. A balanced tree gives roughly O(log n) paths. Inserting already sorted numbers into this simple implementation instead creates a chain and gives O(n) worst-case operations.
Deleting a node requires separate cases for a leaf, one child and two children. For two children, a common strategy uses the smallest key in the right subtree as a replacement, then removes that replacement from its original position. Do not simply disconnect the node and discard its descendants.
Java's TreeSet and TreeMap provide ordered set and map operations through balanced trees. Use them for ordinary application work rather than treating this small educational BST as a replacement for library collections. Custom nodes are valuable when you are learning algorithms or representing a different kind of hierarchy.
Binary Search Trees Summary
- A BST maintains ordering throughout each subtree.
- Return and reconnect subtree roots during insertion.
- Document how equal keys are handled.
- Prefer TreeSet or TreeMap when application code needs maintained ordering.
- Continue with heaps to compare a different ordering structure.
Binary Search Trees Examples
Each example shows the code, the output it produces and what each part does.
Inserting keys into a Java BST
Save this program as LockerTreeExample.java. It uses a static nested Node class so each node needs only its key and child references.
Inserting 30 compares it with 40, then 20. It becomes the right child of 20. It still remains below 40 in the left subtree, satisfying both ordering constraints.
public class LockerTreeExample {
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 void inorder(Node node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.key + " ");
inorder(node.right);
}
public static void main(String[] args) {
Node root = null;
for (int key : new int[]{40, 20, 60, 10, 30}) {
root = insert(root, key);
}
inorder(root);
System.out.println();
}
}10 20 30 40 60Line-by-line explanation
- Lines 8 to 12Insertion creates a node only at an empty position. Returning each existing node preserves the route back to the root.
- Lines 10 to 11Assigning the recursive result updates the correct child reference. Equal keys follow neither branch, so this tree ignores duplicates.
- Lines 15 to 19In-order traversal visits the left subtree, current key and right subtree in that order.
- Lines 23 to 25Reassigning root handles the first insertion when the tree is empty.
Searching without recursion
The following standalone program follows one branch at a time. It does not scan every node.
The method also handles an empty tree: a null starting reference skips the loop and returns false. Search uses constant additional space here because it stores just the current reference and target.
public class LockerSearchExample {
static class Node {
int key;
Node left, right;
Node(int key) { this.key = key; }
}
static boolean contains(Node node, int target) {
while (node != null) {
if (target == node.key) return true;
node = target < node.key ? node.left : node.right;
}
return false;
}
public static void main(String[] args) {
Node root = new Node(40);
root.left = new Node(20);
root.right = new Node(60);
System.out.println(contains(root, 60));
System.out.println(contains(root, 25));
}
}true
falseLine-by-line explanation
- Lines 8 to 13Search stops at a matching key or an empty branch. Each comparison chooses exactly one next node.
- Lines 17 to 19The explicit links construct a valid three-node BST.
- Lines 20 to 21Searching for 60 reaches the right child; searching for 25 reaches an absent child below 20.
Computing the number of nodes
This recursive calculation combines the answers from both subtrees.
public class TreeCountExample {
static class Node {
Node left, right;
}
static int size(Node node) {
if (node == null) return 0;
return 1 + size(node.left) + size(node.right);
}
public static void main(String[] args) {
Node root = new Node();
root.left = new Node();
root.right = new Node();
root.left.right = new Node();
System.out.println(size(root));
}
}4Line-by-line explanation
- Lines 6 to 8An empty subtree contributes zero; a real node contributes one plus both child counts.
- Lines 12 to 15Four distinct node objects form the tree. Their keys are unnecessary for a structural count.
- Line 16The root count combines every descendant exactly once.
Binary Search Trees FAQ
Is a folder hierarchy a binary search tree?
Usually not. A folder can have many children and no numeric left-versus-right ordering rule. It is a tree, but not necessarily binary or searchable by the BST algorithm.
Does sorted traversal prove the tree is balanced?
No. Balance concerns shape and height. A chain can still produce correctly sorted in-order output.
Does Java have a built-in binary search tree?
Yes, inside TreeMap and TreeSet, which use a self-balancing red-black tree. They keep keys sorted and guarantee O(log n) insertion, removal and search, plus navigation methods such as floorKey and ceiling. Use them instead of a hand-built tree in real programs.
How tall is a balanced binary search tree?
About log₂ n levels, so a balanced tree of a million keys is roughly 20 levels deep and any key can be found in about 20 comparisons. Inserting keys in sorted order into a plain BST produces a chain as tall as the number of keys, which is why self-balancing trees exist.
How do I delete a node from a binary search tree?
There are three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children takes the key of its in-order successor, the smallest key in its right subtree, and that successor node is then removed from the right subtree.
Binary Search Trees Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
Where should 25 be inserted into a tree with root 40 and left child 20?
Insert 3, then 4, then 5 into the unbalanced tree. What shape results?
Binary Search Trees Quiz
2 questions to check what you learned.
Which traversal prints increasing keys from this strict BST?
- Left subtree, current node, right subtree
- Current node, left subtree, right subtree
- Right subtree, current node, left subtree
What is the worst-case search time in a plain unbalanced BST?
- O(n)
- Always O(log n)
- O(1)