Binary Tree Basics

A BSP tree is a binary tree, so first let's run through some basic binary tree terminology and concepts. A binary tree is a data structure that contains nodes in a hierarchical structure. Binary trees have the following properties:

Each node has, at most, two children, often called the left child and the right child.
The nodes have data associated with them.
A node with no children is called a leaf.
The node with no parent is called the root node.
A sorted binary tree, often called a binary search tree, contains nodes sorted by their data.

Check out the example sorted binary tree in Screenshot. This is a sorted binary tree, and it contains a list of numbers-1, 3, 5, 6, 8, and 9. Okay, now bear with me in an explanation of a sorted binary tree. For every node, all values less than that node's value are on the left side of that node, and all values greater than that node's value are on the right side of that node. For example, because the root node has the value of 5, every number that is less than 5 is on the left side of the tree, and every number that is greater than 5 is on the right side of the tree. Study the example in Screenshot until you understand this.

Screenshot This example binary tree has three leaves and a depth of 2.

Java graphics 10fig01

Also in Screenshot you'll see that this tree has a depth of 2. The depth, sometimes called the height, is the number of the root's child generations. The example is also well balanced, which means that for every node, the depth of its left side is at most one away from the depth of its right side. A well-balanced sorted binary tree can be quickly searched, without having to look at every piece of data. Now you'll implement a simple binary tree and later use the same concepts to make a BSP tree. You'll use integers as the binary tree's data, just like in the example. Let's start with a node:

public class Node {
 Node left;
 Node right;
 int value;
 public Node(int value) {
 this.value = value;
 }
}

The Node class has an integer value and references to the left and right children (which are initially null, so it has no children). Remember, a node can be a root, a leaf, or just a plain node. Creating a new Node is easy-here, you create a root node:

Node root = new Node(5);

Next, you write a method, insertSorted(), to insert a new value into a sorted tree.

public void insertSorted(Node node, int value) {
 if (value < node.value) {
 if (node.left != null) {
 insertSorted(node.left, value);
 }
 else {
 node.left = new Node(value);
 }
 }
 else if (value > node.value) {
 if (node.right != null) {
 insertSorted(node.right, value);
 }
 else {
 node.right = new Node(value);
 }
 }
 else {
 // do nothing - value already in tree
 }
}

To insert the value 8 into the tree, call the following:

insertSorted(root, 8);

This method uses recursion (or, calls itself) to insert values into the tree. A child node is really a binary tree itself-often called a subtree-so calling something such as insertSorted(node.left, value) just inserts the value into the node's left subtree. Notice that this method doesn't allow duplicates into the tree: If a value is already in the tree, it's not inserted again. Finally, you make a method to print every value in the order they are in the tree. This is called an in-order traversal because, you guessed it, the values are traversed in order.

public void printInOrder(Node node) {
 if (node != null) {
 printInOrder(node.left);
 System.out.println(node.value);
 printInOrder(node.right);
 }
}

To print every value in a tree in order, do this:

printInOrder(root);

Again, this method uses recursion. This method basically says: "For this node, print its left subtree, then print its value, and then print its right subtree." That's it for a quick introduction of binary trees. Next, we move on to the main subject of this chapter and introduce the concept of a BSP tree.