Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 223

If you want, you can put the TreeNode class in its own file, TreeNode.java , and declare it public . However, in our
programs, we will put the TreeNode class in the same file as BinaryTree since it is used only by BinaryTree . To do so,
we must omit the word public and write class TreeNode .

8.5 Building a Binary Tree
Let's write a function to build a binary tree. Suppose we want to build a tree consisting of a single node, like this:

A

The data will be supplied as A @ @ . Each @ denotes the position of a null pointer.
To build the following, we will supply the data as A B @ @ C @ @ :

A

B C

Each node is immediately followed by its left subtree and then its right subtree.
By comparison, to build the following, we will supply the data as A B @ C @ @ @ .

A

B

C

The two @s after C denote its left and right subtrees (null), and the last @ denotes the right subtree of A (null).
And to build the following, we supply the data as C E F @ H @ @ B @ @ G A @ @ N J @ @ K @ @ .

C

G

E

N

F B A

J K

H

Given data in this format, the following function will build the tree and return a pointer to its root:

static TreeNode buildTree(Scanner in) {
String str = in.next();
if (str.equals("@")) return null;
TreeNode p = new TreeNode(new NodeData(str));
p.left = buildTree(in);
p.right = buildTree(in);
return p;
} //end buildTree