Quick Refresher: What is a Binary Tree?

In Module 1, we learned the theory and terminology of trees. Now, it's time to bring those concepts to life! This module is where you'll write your first lines of tree-related code. We will focus on the Binary Tree, the most common and foundational tree structure in computer science.

By the end of this module, you'll have a complete, working Java program that builds a simple binary tree, and you'll understand exactly how the parent-child relationships we discussed are represented in code.

1. Quick Refresher: What is a Binary Tree?

Before we code, let's revisit the definition. A Binary Tree is a specific type of tree where every node has at most two children. These children are referred to as the left child and the right child.

This constraint makes them simpler to implement and is the foundation for more advanced structures like Binary Search Trees (BSTs).

2. The Building Block: Creating the TreeNode Class in Java

Every tree is made of nodes. So, our first step in any Java tree implementation is to create a blueprint for a single node. We'll create a class named TreeNode.

A node needs to do two things:

1. Store some data (we'll use an integer for simplicity).
2. Keep references (or pointers) to its left and right children.

Here is the complete Java TreeNode class:

// TreeNode.java

public class TreeNode {

int data; // The data value stored in the node

TreeNode left; // Reference to the left child

TreeNode right; // Reference to the right child

// Constructor to create a new node with the given data

public TreeNode(int data) {

this.data = data;

this.left = null; // Initially, new nodes have no children

this.right = null;

}

}

Breaking down the code:

• int data;: This variable holds the value of the node.
• TreeNode left; and TreeNode right;: This is the most important concept! These are references to other TreeNode objects. If a node does not have a left child, its left reference will be null. This self-referential structure is what allows us to link nodes together to form a tree.

3. The Manager: Creating the BinaryTree Class

Now that we have a blueprint for a node, we need a class to manage the entire tree. The BinaryTree class will hold a reference to just one thing: the root node. From the root, we can access every other node in the tree.

Let's create the class and then manually build a simple tree to understand the structure. This process is key to understanding the parent-child relationship in tree code.

// BinaryTree.java

public class BinaryTree {

// The root of the binary tree. Our entry point to the tree.

TreeNode root;

public BinaryTree() {

root = null; // A new tree is initially empty

}

public static void main(String[] args) {

// Let's create our first binary tree from scratch

BinaryTree tree = new BinaryTree();

// 1. Create the root node

tree.root = new TreeNode(1);

// 2. Create the children of the root

tree.root.left = new TreeNode(2);

tree.root.right = new TreeNode(3);

// 3. Create the children for the node '2'

tree.root.left.left = new TreeNode(4);

tree.root.left.right = new TreeNode(5);

System.out.println("Binary Tree created successfully!");

// We now have the following tree:

//      1

//     / \

//    2   3

//   / \

//  4   5

}

}

Code Explanation:

• TreeNode root;: This single variable in our BinaryTree class is the handle to the entire tree structure.
• In the main method, we create nodes and manually link them. The line tree.root.left = new TreeNode(2); explicitly says: "Set the left child of the root node (1) to be a new node with the value 2." This is how parent-child links are coded.