Java Binary Trees
A binary tree is one of the most important data structures in programming: a hierarchical structure in which every node has at most two children, called the left child and the right child. Binary trees underpin many other structures and algorithms you will meet in Java, including binary search trees, heaps, and expression trees, and they show up constantly in real systems such as file systems, routing tables, and database indexes. Learning how to build, traverse, search, and reason about binary trees in Java gives you the foundation for almost every advanced data structure that follows.
Overview: What Is a Binary Tree and How Does It Work?
A binary tree is made of nodes. Each node stores a piece of data and two references (sometimes called pointers) to other nodes: a left child and a right child. The topmost node is the root. A node with no children is called a leaf. Any node, together with everything reachable below it, is called a subtree, and the distance from the root to a node is its depth, while the longest path from a node down to a leaf is its height. Unlike an array, a binary tree has no fixed size and no contiguous memory layout — it grows one heap-allocated Node object at a time, and the tree as a whole is really just a single reference to its root node. Everything else is reachable by repeatedly following left and right references.
A plain binary tree does not impose any ordering on its values — you can place data wherever you like. A binary search tree (BST) is a binary tree with one extra rule: for every node, all values in its left subtree are smaller than the node’s value, and all values in its right subtree are larger. That single rule is what makes searching, inserting, and deleting in a BST fast: at each node you only need to look at one side, so a balanced BST supports search, insert, and delete in O(log n) time, compared to O(n) for scanning a list. If the tree becomes lopsided (for example, by inserting already-sorted data one value at a time), it degenerates into something that behaves like a linked list, and operations slow down to O(n). Self-balancing trees such as AVL trees, Red-Black trees, or Java’s own TreeMap/TreeSet solve that problem automatically, but understanding a plain BST first is essential before reaching for those.
Because every subtree is itself a smaller binary tree, recursion is the natural tool for writing tree algorithms. Nearly every method you write for a tree — traversal, search, insertion, computing height — follows the same shape: handle the base case where the node is null, then recurse into node.left and node.right.
Syntax
A binary tree node in Java is typically written as a small class holding a data field and two self-referencing fields:
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}| Part | Meaning |
|---|---|
data |
The value stored in this node (can be any type, not just int) |
left |
Reference to the left child Node, or null if there is none |
right |
Reference to the right child Node, or null if there is none |
| Constructor | Initializes data; left and right default to null automatically |
The tree itself is usually represented by a single variable, often called root, of type Node. An empty tree is simply Node root = null;.
Examples
Example 1: Building a Tree by Hand and Traversing It
public class Main {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
System.out.print("Inorder traversal: ");
inorder(root);
System.out.println();
}
static void inorder(Node node) {
if (node == null) {
return;
}
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
}Output:
Inorder traversal: 4 2 5 1 3 Here the tree is assembled manually by wiring up left and right references, with no ordering rule applied. The inorder method recurses to the deepest left node first, prints it, then unwinds back up through the right side, which is why the output visits node 4 before node 2, and node 2 before the root.
Example 2: A Binary Search Tree with Insert and Search
public class Main {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}
static class BST {
Node root;
void insert(int value) {
root = insertRec(root, value);
}
Node insertRec(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value < node.data) {
node.left = insertRec(node.left, value);
} else if (value > node.data) {
node.right = insertRec(node.right, value);
}
return node;
}
boolean search(int value) {
return searchRec(root, value);
}
boolean searchRec(Node node, int value) {
if (node == null) {
return false;
}
if (node.data == value) {
return true;
}
return value < node.data ? searchRec(node.left, value) : searchRec(node.right, value);
}
void inorder(Node node) {
if (node == null) {
return;
}
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
}
public static void main(String[] args) {
BST tree = new BST();
int[] values = {50, 30, 70, 20, 40, 60, 80};
for (int v : values) {
tree.insert(v);
}
System.out.print("Inorder traversal (sorted): ");
tree.inorder(tree.root);
System.out.println();
System.out.println("Search 40: " + tree.search(40));
System.out.println("Search 90: " + tree.search(90));
}
}Output:
Inorder traversal (sorted): 20 30 40 50 60 70 80
Search 40: true
Search 90: falseThis is a real binary search tree. Every call to insert walks down from the root, going left when the new value is smaller and right when it is larger, until it finds an empty spot. Because the BST property is maintained, an inorder traversal always visits values in ascending order — notice the output is perfectly sorted even though the values were inserted out of order. The search method uses the same left/right logic to decide which subtree can possibly contain the value, skipping half the remaining tree at each step.
Example 3: Level-Order Traversal and Computing Height
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
Node root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);
System.out.print("Level order: ");
levelOrder(root);
System.out.println();
System.out.println("Height: " + height(root));
}
static void levelOrder(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.print(current.data + " ");
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
static int height(Node node) {
if (node == null) {
return -1;
}
return 1 + Math.max(height(node.left), height(node.right));
}
}Output:
Level order: 50 30 70 20 40 60 80
Height: 2Level-order traversal (also called breadth-first traversal) visits the tree row by row instead of diving deep first. It cannot be written with simple recursion the way inorder or preorder can, because recursion naturally follows one branch to the bottom before backtracking. Instead it uses an explicit Queue: a node is removed from the front, printed, and its children are added to the back, which guarantees nodes are visited in the order they were discovered. The height method shows the recursive pattern again: an empty subtree has height -1, a leaf has height 0, and every other node's height is one more than the taller of its two children.
How It Works Step by Step (Under the Hood)
Every Node you create with new Node(value) is allocated on the heap, just like any other Java object; the root variable (and every left/right field) is just a reference pointing at one of these heap objects, or null. There is no special JVM support for trees — a binary tree is simply ordinary objects linked together, and the JVM's garbage collector reclaims a Node automatically once nothing in the tree points to it anymore (for example, after it is removed during a deletion).
When a recursive method such as insertRec or inorder runs, each call adds a new frame to the JVM's call stack, holding that call's local variables (including the node parameter). Descending into node.left pushes another frame; hitting the null base case stops the descent and the stack unwinds, executing the remaining statements of each frame in reverse order. This is exactly why inorder traversal (left, visit, right) prints values in ascending order for a BST, while preorder (visit, left, right) is useful for copying or serializing a tree structure, and postorder (left, right, visit) is useful for safely deleting a tree bottom-up, since children are processed before their parent.
| Traversal | Order | Typical use |
|---|---|---|
| Preorder | root, left, right | Copying or serializing a tree |
| Inorder | left, root, right | Producing sorted output from a BST |
| Postorder | left, right, root | Deleting or freeing a tree safely |
| Level order | row by row, top to bottom | Shortest-path / breadth-first problems |
On a balanced tree with n nodes, the height is roughly log2(n), so insert and search only need to follow that many left/right decisions — O(log n). On a skewed tree (for example, one built by inserting 1, 2, 3, 4, 5 in order into a BST), every node has only a right child, the height becomes n, and every operation degrades to O(n), identical to a linked list.
Common Mistakes
Mistake 1: Comparing the node itself instead of its data field
Wrong:
Node insertRec(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (node < value) {
node.right = insertRec(node.right, value);
} else {
node.left = insertRec(node.left, value);
}
return node;
}This will not even compile: node is a reference of type Node, and Java's < operator only works on numeric types, not on objects. The bug comes from forgetting that the comparison must be against the node's data field, not the node reference itself.
Corrected:
Node insertRec(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value > node.data) {
node.right = insertRec(node.right, value);
} else {
node.left = insertRec(node.left, value);
}
return node;
}Mistake 2: Forgetting the null check in a recursive traversal
Wrong:
static void inorder(Node node) {
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}Every recursive tree method needs a base case, or it will throw a NullPointerException as soon as it reaches a leaf node's null child. Without the check, calling inorder(node.left) on a leaf tries to read .left off a node whose left child is null, then immediately calls inorder again on that null reference and crashes trying to read node.data.
Corrected:
static void inorder(Node node) {
if (node == null) {
return;
}
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}Best Practices
- Always write the
nullcheck as the very first line of any recursive tree method — it is the base case that stops the recursion. - Keep the
Nodeclass as a private static nested class inside the tree class so the internal representation is not exposed to callers. - Use inorder traversal to read a BST in sorted order, preorder to copy or export the tree's shape, postorder when deleting nodes, and level order (with a
Queue) when you need shortest-path or row-by-row behavior. - If your input is likely to arrive already sorted, avoid inserting it directly into a plain BST — it degenerates into a linked list; consider Java's built-in
TreeMap/TreeSet, which are self-balancing. - Be cautious with deep recursion on very large or heavily skewed trees; extremely deep recursion can exhaust the call stack and throw a
StackOverflowError. An iterative traversal using an explicitStackavoids that risk. - When deleting a node with two children, replace its value with either its inorder successor (smallest value in the right subtree) or inorder predecessor (largest value in the left subtree) to keep the BST property intact.
Practice Exercises
- Write a method
int countNodes(Node node)that returns the total number of nodes in a binary tree using recursion. - Write a method
boolean isValidBST(Node node, Integer min, Integer max)that checks whether a binary tree satisfies the binary search tree property at every node. - Add a method
int findMin()to theBSTclass from Example 2 that returns the smallest value in the tree. Hint: from the root, keep followingleftuntil you reach a node whoseleftisnull.
Summary
- A binary tree is built from
Nodeobjects, each holding data and references to a left and right child; the tree itself is just a reference to the root node. - A binary search tree adds the ordering rule that left subtree values are smaller and right subtree values are larger than the current node, enabling fast O(log n) search on balanced trees.
- Recursion is the natural way to write tree algorithms because every subtree is itself a smaller binary tree; always start with a
nullbase case. - Inorder, preorder, and postorder traversals are depth-first and recursive; level-order traversal is breadth-first and needs an explicit
Queue. - Unbalanced trees degrade to O(n) performance; self-balancing structures like
TreeMapavoid this in production code.
