Binary Tree Representation — Represent basic binary trees with node classes (intro) - Java

SECTION 1

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.

1956 • Binary Trees Formalized

Computer scientists formalized the concept of binary trees as mathematical structures for organizing data. Early research explored how branching hierarchies could speed up searching compared to linear lists.

1960 • Binary Search Trees

Researchers developed the binary search tree (BST), a special binary tree where left children are smaller and right children are larger. This allowed searches in O(log n) time, a major improvement over scanning every element.

1962 • AVL Trees Introduced

Adelson-Velsky and Landis published the first self-balancing binary search tree, ensuring the tree stays efficient even as data is inserted and removed. This built directly on the basic binary tree concept.

1995 • Java Released

Sun Microsystems released Java, whose object-oriented design made implementing tree node classes especially clean. Java's reference-based objects naturally model the parent-child links in a tree.

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.

SECTION 2

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

The basic building block of a binary tree. In Java, a node is an object that holds data and two references: left and right.

Root

The single starting node at the top of the tree. Every other node is reachable by following left or right references from the root.

Left & Right Children

Each node can point to at most two children. A child that doesn't exist is represented as null in Java.

Leaf Node

A node where both the left and right references are null. Leaf nodes are the "endpoints" of the tree.

Edge

A connection between a parent node and one of its children. A tree with n nodes always has exactly n − 1 edges.

✦

KEY TAKEAWAY

Think of a binary tree like an upside-down family tree. The root is the single ancestor at the top. Each person (node) can have at most two children. A leaf is someone with no kids. In Java, you model this by creating a TreeNode class where each object "knows" its data and has two references pointing to its children — or null if a child doesn't exist.

SECTION 3

Visual Explanation — Anatomy of a Binary Tree

This diagram shows a binary tree with root value 10. The cyan node at the top is the root. Purple and pink nodes are internal nodes at depth 1, and the yellow nodes at the bottom are leaf nodes. Notice that node 15 only has a right child — its left child is 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.

SECTION 4

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

ℹ

Java Code — TreeNode Class

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

💡

Java Code — Building the Tree from the Diagram

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.

NUMBER OF EDGES

edges = n − 1

A tree with n nodes always has exactly n − 1 edges, because every node except the root has exactly one parent.

MAXIMUM NODES AT DEPTH d

max nodes at depth d = 2ᵈ

At depth 0 (root), there is 2⁰ = 1 node. At depth 1, there can be up to 2¹ = 2 nodes. At depth 2, up to 2² = 4 nodes, and so on.

SECTION 5

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.

Each box represents a 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.

SECTION 6

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.

ℹ

Problem

Build a binary tree with root 42, left child 17, right child 63. Node 17 has a right child of 25. Node 63 has a left child of 50 and a right child of 78. Identify the root, all leaves, the depth of node 50, and the total number of edges.

Building and Analyzing a Binary Tree

1
Step 1 — Define the TreeNode class

We use the same class definition from earlier: class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; this.left = null; this.right = null; } }
2
Step 2 — Create the root node

Create the root: TreeNode root = new TreeNode(42);. This gives us a single node with data 42 and both children set to null.

Root node created: data = 42, left = null, right = null
3
Step 3 — Attach left and right children to root

root.left = new TreeNode(17); and root.right = new TreeNode(63);. Now the root has two children.

Tree now has 3 nodes at depths 0 and 1
4
Step 4 — Attach grandchildren

Node 17 gets a right child: 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.

Tree now has 6 nodes total
5
Step 5 — Analyze the structure

Root: node 42 (the entry point). Leaves: nodes 25, 50, and 78 — each has both children as null. Depth of node 50: Start at root (depth 0), go right to 63 (depth 1), go left to 50 (depth 2). So node 50 is at depth 2. Edges: With n = 6 nodes, edges = 6 − 1 = 5.

Root: 42 | Leaves: 25, 50, 78 | Depth of 50: 2 | Edges: 5

SECTION 7

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

Comparison of linked vs. array representations of binary trees

✦

KEY TAKEAWAY

Think of linked nodes like houses connected by roads — each house has its own address, and you navigate by following directions (references). An array representation is like houses in a numbered row — you find neighbors using math on house numbers. Linked nodes are more flexible for oddly-shaped trees, while arrays are faster for compact, balanced trees. For learning binary trees, the linked (node class) approach is the standard starting point.

SECTION 8

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

Advanced structures built on the basic binary tree node

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.

💡

Looking Ahead

The TreeNode class can also be made generic using Java generics (e.g., TreeNode<T>) so it can store any data type — not just integers. You'll explore this once you're comfortable with Java generics.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

In the 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?

Show answer

When both left and right are null, it means the node has no children. This is called a leaf node. Leaf nodes are important because they represent the endpoints of the tree — there are no further branches to follow. When traversing a tree recursively, reaching a null reference is the base case that tells the algorithm to stop going deeper.

Question 2: BASIC CALCULATION

A binary tree has 9 nodes. How many edges does it have? If the tree is perfectly balanced (a complete binary tree), what is its height?

Show answer

Using the formula edges = n − 1, the tree has 9 − 1 = 8 edges. For the height of a complete binary tree, we use the fact that a complete binary tree of height h can hold up to

2^{h+1}

− 1 nodes. A height of 3 can hold up to 2⁴ − 1 = 15 nodes, and a height of 2 holds up to 2³ − 1 = 7 nodes. Since 9 nodes don't fit in height 2 but fit in height 3, the height is 3. You can also reason that depth 0 has 1 node, depth 1 has 2, depth 2 has 4, and depth 3 has the remaining 2 nodes.

Question 3: INTERMEDIATE

Write Java code to build this binary tree: root = 100, root's left child = 40, root's right child = 120, node 40's left child = 20, node 120's left child = 110, node 120's right child = 150. Then write a boolean expression that checks whether node 120 is a leaf.

Show answer

The code would be:

TreeNode root = new TreeNode(100); root.left = new TreeNode(40); root.right = new TreeNode(120); root.left.left = new TreeNode(20); root.right.left = new TreeNode(110); root.right.right = new TreeNode(150);

To check if node 120 is a leaf, you would write: root.right.left == null && root.right.right == null. This evaluates to false because node 120 has children (110 and 150). Nodes 20, 110, and 150 are the actual leaves in this tree.

Question 4: APPLIED

Imagine you're building a decision tree for a simple game: "Is the number greater than 50?" If yes, go right and ask "Is it greater than 75?" If no, go left and ask "Is it greater than 25?" Each leaf node stores a message like "Number is between 26 and 50". Design a TreeNode class that stores a String instead of an int, and write the code to build this decision tree with at least the first two levels.

Show answer

You would modify the TreeNode class to use String:

class TreeNode { String data; TreeNode left; TreeNode right; TreeNode(String data) { this.data = data; this.left = null; this.right = null; } }

Then build the tree:

TreeNode root = new TreeNode("Greater than 50?"); root.left = new TreeNode("Greater than 25?"); root.right = new TreeNode("Greater than 75?");

You'd continue adding leaf nodes like root.left.left = new TreeNode("Number is 1-25"); and so on. This example shows that the TreeNode pattern works for any data type — the structure of left/right references remains the same regardless of what's stored in each node.

Question 5: CRITICAL THINKING

Consider a binary tree where you want each node to also have a reference to its parent (so you can navigate both down and up). How would you modify the TreeNode class? What should the parent reference of the root node be? Discuss one advantage and one disadvantage of adding parent references.

Show answer

You would add a TreeNode parent field to the class. The root's parent should be null since it has no parent. When attaching a child, you'd also set child.parent = this;. One advantage is that you can traverse upward from any node to the root without needing to search from the top — this is useful for algorithms like finding the lowest common ancestor. One disadvantage is that every insertion and deletion now requires updating extra references (the parent pointer), which adds complexity and increases the chance of bugs. It also uses more memory since each node stores an additional reference.

SUMMARY

Summary — Binary Tree Representation with Node Classes

Summary

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.