Historical Context & Motivation
Before computers had gigabytes of memory or colorful graphical interfaces, early programmers needed efficient ways to organize and search through data. Flat structures like arrays and lists worked well for simple sequences, but they struggled when data had a natural hierarchy — like a family tree, a file system, or a decision-making flowchart. The binary tree emerged as an elegant solution: a data structure where each element can branch into at most two sub-elements, creating a tree-like shape that enables fast searching, sorting, and organization.
The central question this lesson addresses is straightforward yet fundamental: How do we represent a binary tree in Java code using classes and object references? Once you understand this representation, you'll have the foundation for building search trees, heaps, expression trees, and many other powerful structures.
Core Principles & Definitions
A binary tree is built from individual pieces called nodes. Each node stores a piece of data (like a number or a string) and holds references to up to two other nodes — its left child and its right child. If a child doesn't exist, that reference is set to null. The topmost node is called the root, and nodes with no children are called leaves.
Node
left and right.Root
Left & Right Children
null in Java.Leaf Node
null. Leaf nodes are the "endpoints" of the tree.Edge
TreeNode class where each object "knows" its data and has two references pointing to its children — or null if a child doesn't exist.Visual Explanation — Anatomy of a Binary Tree
null.In the diagram above, every connection (line) between two nodes is called an edge. The tree has 6 nodes and 5 edges, which follows the rule that a tree with n nodes always has n − 1 edges. The depth of a node is how many edges separate it from the root. The root has depth 0, nodes 5 and 15 have depth 1, and the leaves have depth 2. The overall height of this tree is 2, which equals the depth of the deepest leaf.
How It Works — The TreeNode Class in Java
In Java, we represent each node of a binary tree as an object of a custom class. The most common approach is to define a class called TreeNode with three fields: an int (or other type) for the data, and two TreeNode references for the left and right children. This is a self-referential class — the class has fields whose type is the class itself. This might seem circular, but Java handles it cleanly because object variables are actually references (pointers), not the objects themselves.
The TreeNode Class Definition
class TreeNode {
int data;
TreeNode left;
TreeNode right;
// Constructor
TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}Let's break this class down. The field int data stores the value held by this node. The fields TreeNode left and TreeNode right are references to the node's children. When a new node is created using the constructor, both children start as null, meaning the node begins its life as a leaf. You then connect nodes by assigning their left and right fields to other TreeNode objects.
Building a Tree by Connecting Nodes
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(20);This code constructs exactly the tree shown in the earlier diagram. The variable root holds a reference to the top node (data = 10). We then attach children by assigning to root.left and root.right. Notice that root.right.left is never assigned, so it remains null — exactly as we described for node 15 having no left child.
Memory Layout — How Java Stores Tree Nodes
Understanding how Java stores tree nodes in memory will help you reason about how the tree works at runtime. Each TreeNode object lives on the heap (Java's memory area for objects). The variable root in your code is a reference — essentially an address that tells Java where to find the root node object. The root's left and right fields are also references that point to other node objects elsewhere in memory. The nodes don't have to be stored next to each other — they're connected purely through these references.
TreeNode object in Java's heap memory. Arrows represent references. The node 15 shows its left field as null (red), meaning it has no left child. Leaf nodes have both children set to null.The diagram above shows what's really happening under the hood. Each rectangle is a TreeNode object at some memory address. The arrows represent the reference fields, and null values (shown in red) indicate the absence of a child. This is the linked representation of a binary tree — nodes are scattered across memory and connected by references, similar to how a linked list works but with two links instead of one.
Worked Example — Building and Reading a Binary Tree
Let's walk through a complete example: writing the Java code to build a specific binary tree, then answering questions about its structure.
class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; this.left = null; this.right = null; } }TreeNode root = new TreeNode(42);. This gives us a single node with data 42 and both children set to null.root.left = new TreeNode(17); and root.right = new TreeNode(63);. Now the root has two children.root.left.right = new TreeNode(25);. Node 63 gets both children: root.right.left = new TreeNode(50); and root.right.right = new TreeNode(78);. Note that root.left.left is never assigned, so it stays null.Linked Nodes vs. Array Representation
The node-class approach we've been studying is called the linked representation. There's an alternative approach where you store all tree values in an array, using index math to find children. Each method has trade-offs, which the table below summarizes.
| Feature | Linked (Node Classes) | Array Representation |
|---|---|---|
| Memory usage | Efficient — only allocates memory for nodes that exist | Can waste space if tree is sparse (many nulls) |
| Adding a node | Easy — just create a new object and assign a reference | May require resizing the array |
| Accessing children | Follow .left / .right references | Calculate index: left child at 2i + 1, right at 2i + 2 |
| Flexibility | Works well for any shape of tree | Best for complete or nearly complete trees (like heaps) |
| Intuition | Closely mirrors the conceptual tree diagram | More abstract; requires index arithmetic |
Connection to Advanced Tree Structures
The simple TreeNode class you learned today is the starting point for many powerful data structures. By adding rules about how data is organized within the tree, you get specialized structures that solve different problems with impressive efficiency.
| Structure | Extra Rule on Top of Basic Binary Tree | What It's Used For |
|---|---|---|
| Binary Search Tree (BST) | Left child < parent < right child for all nodes | Fast searching, insertion, and deletion — O(log n) on average |
| Heap | Parent ≤ children (min-heap) or parent ≥ children (max-heap) | Priority queues, efficient sorting (heapsort) |
| AVL / Red-Black Tree | BST rules + self-balancing to keep height minimal | Guaranteed O(log n) operations even in worst case |
| Expression Tree | Operators at internal nodes, operands at leaves | Representing and evaluating math expressions like (3 + 5) × 2 |
Every one of these structures uses the same fundamental idea — a TreeNode with data, a left reference, and a right reference. The only thing that changes is the rules governing how nodes are arranged. Mastering the basic node class gives you a solid foundation for all of these. In upcoming lessons, you'll learn how to traverse trees (visit every node in a specific order), search for values, and build binary search trees.
TreeNode<T>) so it can store any data type — not just integers. You'll explore this once you're comfortable with Java generics.Practice Problems
TreeNode class, what does it mean when node.left == null and node.right == null? What is such a node called, and why is it important?String instead of an int, and write the code to build this decision tree with at least the first two levels.TreeNode class? What should the parent reference of the root node be? Discuss one advantage and one disadvantage of adding parent references.Summary — Binary Tree Representation with Node Classes
A binary tree is a hierarchical data structure where each node stores data and has at most two children: a left child and a right child. In Java, we represent this with a self-referential TreeNode class containing an int data field and two TreeNode reference fields. Missing children are represented as null. The topmost node is the root, and nodes with no children are leaves.
You build a tree by creating node objects and connecting them through their left and right fields. This linked representation is flexible and mirrors the conceptual tree structure directly. A tree with n nodes has exactly n − 1 edges, and the maximum nodes at depth d is 2ᵈ. This foundational class is the basis for more specialized structures like binary search trees, heaps, and expression trees.