Binary Trees - Building Java Programs: A Back to Basics Approach - page 982

of the overall root, and the grandchildren of the overall root. This notion of levels
leads us to the concept of the depth of an individual node (how many levels away
from the root it is) and the overall height of the tree (how many levels it has).

Node and Tree Classes
When we studied linked lists, we found that each was built from a fairly simple
building block that looks like this:

data
18

next

Our basic building block for a binary tree will be similar, but instead of one link, it
will have two:

data
18

left right

As we did with linked lists, we will first study how to manipulate a binary tree of
simple int values. Here is a class definition for our binary tree nodes.

1 // Class for storing a single node of a binary tree of ints
2
3 public class IntTreeNode {
4 public int data;
5 public IntTreeNode left;
6 public IntTreeNode right;
7
8 // constructs a leaf node with given data
9 public IntTreeNode( int data) {
10 this (data, null, null);
11 }
12
13 // constructs a branch node with given data, left subtree,
14 // right subtree
15 public IntTreeNode( int data, IntTreeNode left,
16 IntTreeNode right) {
17 this .data = data;
18 this .left = left;
19 this .right = right;
20 }
21 }