Trees and Binary Search Trees in Java
A school's organization chart starts with the principal at the top. Below are the vice principals, below them the heads of department, and below them the teachers. Everyone except the principal has exactly one boss, and there are no loops. That shape is a tree. A binary search tree adds one simple rule to it: everything on the left of a node is smaller, and everything on the right is larger. That rule turns finding a value into a short walk downward, just like binary search. In this lesson, you will learn tree terms, build a binary search tree in Java with insert, search and the three traversals, and see when it is fast and when it isn't.
What Is a Tree?
A tree in Java is a hierarchical data structure that is used to store elements in nodes connected by edges, where each node has one parent (except the top node) and any number of children.
| Term | Meaning |
|---|---|
| Root | The top node; it has no parent |
| Parent, child | A node directly above or below another |
| Leaf | A node with no children |
| Subtree | A node together with everything below it |
| Depth of a node | Number of edges from the root down to it |
| Height of a tree | Number of levels: the longest path from the root to a leaf, counting nodes |
| Binary tree | A tree in which every node has at most two children: left and right |
What Is a Binary Search Tree?
A binary search tree (BST) is a binary tree in which, for every node:
- all keys in its left subtree are smaller than the node's key, and
- all keys in its right subtree are larger.
Building a BST in Java
Let's see a BST of int keys with insert, search, the three depth-first traversals and height.
public class MarksTree {
private 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); // empty spot found
if (key < node.key) node.left = insert(node.left, key);
else if (key > node.key) node.right = insert(node.right, key);
return node; // duplicates ignored
}
boolean contains(int key) {
Node node = root;
int steps = 0;
while (node != null) {
steps++;
if (key == node.key) {
System.out.println(" found " + key + " in " + steps
+ " steps");
return true;
}
node = key < node.key ? node.left : node.right;
}
System.out.println(" " + key + " missing after " + steps + " steps");
return false;
}
void inOrder(Node n, StringBuilder out) { // left, node, right
if (n == null) return;
inOrder(n.left, out);
out.append(n.key).append(' ');
inOrder(n.right, out);
}
void preOrder(Node n, StringBuilder out) { // node, left, right
if (n == null) return;
out.append(n.key).append(' ');
preOrder(n.left, out);
preOrder(n.right, out);
}
void postOrder(Node n, StringBuilder out) { // left, right, node
if (n == null) return;
postOrder(n.left, out);
postOrder(n.right, out);
out.append(n.key).append(' ');
}
int height(Node n) {
return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right));
}
public static void main(String[] args) {
MarksTree tree = new MarksTree();
for (int k : new int[] {50, 30, 70, 20, 40, 60, 80}) {
tree.insert(k);
}
tree.contains(60);
tree.contains(65);
StringBuilder in = new StringBuilder();
StringBuilder pre = new StringBuilder();
StringBuilder post = new StringBuilder();
tree.inOrder(tree.root, in);
tree.preOrder(tree.root, pre);
tree.postOrder(tree.root, post);
System.out.println("in-order: " + in.toString().trim());
System.out.println("pre-order: " + pre.toString().trim());
System.out.println("post-order: " + post.toString().trim());
System.out.println("height: " + tree.height(tree.root));
}
} found 60 in 3 steps
65 missing after 3 steps
in-order: 20 30 40 50 60 70 80
pre-order: 50 30 20 40 70 60 80
post-order: 20 40 30 60 80 70 50
height: 3Explanation:
insertwalks down: left if the key is smaller, right if larger, until it reaches an empty spot (null), where it creates the node. The recursive version returns the (possibly new) subtree root, so links are updated automatically.containsfinds 60 in 3 steps (50, 70, 60), as in the picture. For 65 it walks 50, 70, 60 and then reaches an empty right child of 60, so 65 is missing.- In-order traversal (left, node, right) prints the keys in sorted order. This is a key property of every BST.
- Pre-order (node first) lists a parent before its children: useful for copying a tree. Post-order (node last) lists children before their parent: useful for deleting a tree or computing sizes.
heightis 1 plus the taller subtree's height: here 3 levels.
Balanced and Unbalanced Trees
A BST is only fast if it is balanced: roughly the same number of nodes on each side. The shape depends on the insertion order.
public class Unbalanced {
record Node(int key, Node left, Node right) {}
static Node insert(Node n, int key) {
if (n == null) return new Node(key, null, null);
return key < n.key()
? new Node(n.key(), insert(n.left(), key), n.right())
: new Node(n.key(), n.left(), insert(n.right(), key));
}
static int height(Node n) {
if (n == null) return 0;
return 1 + Math.max(height(n.left()), height(n.right()));
}
public static void main(String[] args) {
Node mixed = null, sorted = null;
for (int k : new int[] {50, 30, 70, 20, 40, 60, 80}) {
mixed = insert(mixed, k);
}
for (int k : new int[] {20, 30, 40, 50, 60, 70, 80}) {
sorted = insert(sorted, k);
}
System.out.println("mixed order height: " + height(mixed));
System.out.println("sorted order height: " + height(sorted));
}
}mixed order height: 3
sorted order height: 7Explanation: the same seven keys give a tree of height 3 when inserted in a mixed order, but height 7 when inserted in sorted order: every node has only a right child, so the "tree" is really a linked list and search becomes O(n). Self-balancing trees fix this by rotating nodes after each insert. Java's TreeMap and TreeSet use a red-black tree, which keeps the height at most about 2 log₂ n.
Complexity
| Operation | Balanced BST | Unbalanced BST (worst) | TreeMap (red-black) |
|---|---|---|---|
| Search, insert, delete | O(log n) | O(n) | O(log n) guaranteed |
| In-order traversal | O(n) | O(n) | O(n) |
| Space | O(n) | O(n) | O(n) |
Interview Corner
Which traversal of a BST gives sorted output?
In-order: left subtree, node, right subtree.
What is the worst case for a plain BST and why?
O(n) for search, when keys are inserted in sorted order and the tree becomes a chain.
How do you check whether a binary tree is a valid BST?
Walk it in order and check that each key is larger than the previous one, or pass down a valid (min, max) range to each node.
Practice
- Easy: Add methods
min()andmax()toMarksTree. Hint: the smallest key is as far left as you can go. - Harder: Add
countInRange(int low, int high)that counts keys betweenlowandhighwithout visiting subtrees that can't contain them. Test it with 35 and 65 (answer: 3).
Key Takeaways
Was this tutorial helpful?