Paul NgugiA tree is a classic data structure with many important applications. A tree provides a hierarchical organization in which data are stored in the nodes. This chapter introduces binary search trees. You will learn how to construct a binary search tree, how to search an element, insert an element, delete an element, and traverse elements in a binary search tree. You will also learn how to define and implement a custom data structure for a binary search tree.
A binary search tree can be implemented using a linked structure. Recall that lists, stacks, and queues are linear structures that consist of a sequence of elements. A binary tree is a hierarchical structure. It either is empty or consists of an element, called the root, and two distinct binary trees, called the left subtree and right subtree, either or both of which may be empty. Examples of binary trees are shown in Figure below.
The length of a path is the number of the edges in the path. The depth of a node is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. Siblings are nodes that share the same parent node. The root of a left (right) subtree of a node is called a left (right) child of the node. A node without children is called a leaf. The height of a nonempty tree is the length of the path from the root node to its furthest leaf. The height of a tree that contains a single node is 0. Conventionally, the height of an empty tree is —1. Consider the tree in Figure above (a). The length of the path from node 60 to 45 is 2. The depth of node 60 is 0, the depth of node 55 is 1, and the depth of node 45 is 2. The height of the tree is 2. Nodes 45 and 57 are siblings. Nodes 45, 57, 67, and 107 are at the same level.
A special type of binary tree called a binary search tree (BST) is often useful. A BST (with no duplicate elements) has the property that for every node in the tree, the value of any node in its left subtree is less than the value of the node, and the value of any node in its right subtree is greater than the value of the node. The binary trees in Figure above are all BSTs.
Representing Binary Search Trees
A binary tree can be represented using a set of linked nodes. Each node contains a value and two links named left and right that reference the left child and right child, respectively, as shown in Figure below.
A node can be defined as a class, as follows:
class TreeNode<E> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
The variable root refers to the root node of the tree. If the tree is empty, root is null. The following code creates the first three nodes of the tree in Figure above.
// Create the root node
TreeNode<Integer> root = new TreeNode<>(60);
// Create the left child node
root.left = new TreeNode<>(55);
// Create the right child node
root.right = new TreeNode<>(100);
Searching for an Element
To search for an element in the BST, you start from the root and scan down from it until a match is found or you arrive at an empty subtree. The algorithm is described in the code below. Let current point to the root (line 2). Repeat the following steps until current is null (line 4) or the element matches current.element (line 12).
- If element is less than current.element, assign current.left to current (line 6).
- If element is greater than current.element, assign current.right to current (line 9).
- If element is equal to current.element, return true (line 12).
If current is null, the subtree is empty and the element is not in the tree (line 14).
1 public boolean search(E element) {
2 TreeNode<E> current = root; // Start from the root
3
4 while (current != null)
5 if (element < current.element) {
6 current = current.left; // Go left
7 }
8 else if (element > current.element) {
9 current = current.right; // Go right
10 }
11 else // Element matches current.element
12 return true; // Element is found
13
14 return false; // Element is not in the tree
15 }
Inserting an Element into a BST
To insert an element into a BST, you need to locate where to insert it in the tree. The key idea is to locate the parent for the new node. The code below gives the algorithm.
1 boolean insert(E e) {
2 if (tree is empty)
3 // Create the node for e as the root;
4 else {
5 // Locate the parent node
6 parent = current = root;
7 while (current != null)
8 if (e < the value in current.element) {
9 parent = current; // Keep the parent
10 current = current.left; // Go left
11 }
12 else if (e > the value in current.element) {
13 parent = current; // Keep the parent
14 current = current.right; // Go right
15 }
16 else
17 return false; // Duplicate node not inserted
18
19 // Create a new node for e and attach it to parent
20
21 return true; // Element inserted
22 }
23 }
If the tree is empty, create a root node with the new element (lines 2–3). Otherwise, locate the parent node for the new element node (lines 6–17). Create a new node for the element and link this node to its parent node. If the new element is less than the parent element, the node for the new element will be the left child of the parent. If the new element is greater than the parent element, the node for the new element will be the right child of the parent.
For example, to insert 101 into the tree in Figure above, after the while loop finishes in the algorithm, parent points to the node for 107, as shown in Figure below (a). The new node for 101 becomes the left child of the parent. To insert 59 into the tree, after the while loop finishes in the algorithm, the parent points to the node for 57, as shown in Figure below (b). The new node for 59 becomes the right child of the parent.
Tree Traversal
Tree traversal is the process of visiting each node in the tree exactly once. There are several ways to traverse a tree. This section presents inorder, postorder, preorder, depth-first, and breadth-first traversals.
With inorder traversal, the left subtree of the current node is visited first recursively, then the current node, and finally the right subtree of the current node recursively. The inorder traversal displays all the nodes in a BST in increasing order.
With postorder traversal, the left subtree of the current node is visited recursively first, then recursively the right subtree of the current node, and finally the current node itself. An application of postorder is to find the size of the directory in a file system. As shown in Figure below, each directory is an internal node and a file is a leaf node. You can apply postorder to get the size of each file and subdirectory before finding the size of the root directory.
With preorder traversal, the current node is visited first, then recursively the left subtree of the current node, and finally the right subtree of the current node recursively. Depth-first traversal is the same as preorder traversal. An application of preorder is to print a structured document. As shown in Figure below, you can print a book’s table of contents using preorder traversal.
You can reconstruct a binary search tree by inserting the elements in their preorder. The reconstructed tree preserves the parent and child relationship for the nodes in the original binary search tree.
With breadth-first traversal, the nodes are visited level by level. First the root is visited, then all the children of the root from left to right, then the grandchildren of the root from left to right, and so on.
For example, in the tree in Figure above (b), the inorder is
45 55 57 59 60 67 100 101 107
The postorder is
45 59 57 55 67 101 107 100 60
The preorder is
60 55 45 57 59 100 67 107 101
The breadth-first traversal is
60 55 100 45 57 67 107 59 101
You can use the following tree to help remember inorder, postorder, and preorder. The inorder is 1 + 2, the postorder is 1 2 +, and the preorder is + 1 2.
The BST Class
Following the design pattern of the Java Collections Framework API, we use an interface named Tree to define all common operations for trees and provide an abstract class named AbstractTree that partially implements Tree, as shown in Figure below.
A concrete BST class can be defined to extend AbstractTree, as shown in Figure below.
The codes below give the implementations for Tree, AbstractTree, and BST.
Tree.java
AbstractTree.java
BST.java
package demo;
public class BST<E extends Comparable<E>> extends AbstractTree<E> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary search tree */
public BST() {}
/** Create a binary search tree from an array of objects */
public BST(E[] objects) {
for(int i = 0; i < objects.length; i++)
insert(objects[i]);
}
@Override /** Return true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;
}
@Override /** Insert element e into the binary search tree.
* Return true if the element is inserted successfully. */
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted successfully
}
protected TreeNode<E> createNewNode(E e){
return new TreeNode<>(e);
}
@Override /** Inorder traversal from the root */
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
@Override /** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Postorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
@Override /** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Preorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** This inner class is static, because it does not access
* any instance members defined in its outer class */
public static class TreeNode<E extends Comparable<E>>{
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
@Override /** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array list of nodes
}
@Override /** Delete an element from the binary search tree.
* Return true if the element is deleted successfully.
* Return false if the element is not in the tree. */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left child
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child.
// Locate the rightmost node in the left subtree of
// the current node and also its parent.
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element deleted successfully
}
@Override /** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
@Override /** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
@Override /** Get the current element and move to the next */
public E next() {
return list.get(current++);
}
@Override /** Remove the current element */
public void remove() {
// delete(list.get(current)); // Delete the current element
// list.clear(); // Clear the list
// inorder(); // Rebuild the list
throw new UnsupportedOperationException
("Removing an element from the iterator is not supported");
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
The insert(E e) method (lines 36–64) creates a node for element e and inserts it into the tree. If the tree is empty, the node becomes the root. Otherwise, the method finds an appropriate parent for the node to maintain the order of the tree. If the element is already in the tree,
the method returns false; otherwise it returns true.
The inorder() method (lines 71–81) invokes inorder(root) to traverse the entire tree. The method inorder(TreeNode root) traverses the tree with the specified root. This is a recursive method. It recursively traverses the left subtree, then the root, and finally the right subtree. The traversal ends when the tree is empty.
The preorder() method (lines 84–94) and the postorder() method (lines 97–107) are implemented similarly using recursion.
The path(E e) method (lines 131–148) returns a path of the nodes as an array list. The path starts from the root leading to the element. The element may not be in the tree. For example, in Figure below (a), path(45) contains the nodes for elements 60, 55, and 45, and path(59) contains the nodes for elements 60, 55, and 57.
The implementation of delete() and iterator() (lines 155–269) will be discussed in Deleting Elements from a BST and Iterators.
The code below gives an example that creates a binary search tree using BST (line 7). The program adds strings into the tree (lines 8–14), traverses the tree in inorder, postorder, and preorder (lines 17–23), searches for an element (line 26), and obtains a path from the node containing Peter to the root (lines 30–32).
Inorder (sorted): Adam Daniel George Jones Michael Peter Tom
Postorder: Daniel Adam Jones Peter Tom Michael George
Preorder: George Adam Daniel Michael Jones Tom Peter
The number of nodes is 7
Is Peter in the tree? true
A path from the root to Peter is: George Michael Tom Peter
Inorder (sorted): 1 2 3 4 5 6 7 8
The program checks path != null in line 31 to ensure that the path is not null before invoking path.get(i). This is an example of defensive programming to avoid potential runtime errors.
The program creates another tree for storing int values (line 35). After all the elements are inserted in the trees, the trees should appear as shown in Figure below.
If the elements are inserted in a different order (e.g., Daniel, Adam, Jones, Peter, Tom, Michael, George), the tree will look different. However, the inorder traversal prints elements in the same order as long as the set of elements is the same. The inorder traversal displays a sorted list.
