It's time to dig into inserting, finding, and removing data in a BST in Java.
Insert Data
Unlike adding data to a linked list, you don't need to pick where to insert data in a tree. Adding data always starts at the root of the tree:
/**
* Adds data to an empty tree.
* If the tree is not empty, it calls an overloaded recursive insert() method
* to find the appropriate place to insert the data
*
* @param data to be added
*/
public void insert(T data) {
// if the tree is empty, create a new root node
if (this.root == null) {
this.root = new Node(data);
}
// start the recursive insert() method,
// passing the data and the "root" node
else {
insert(data, root);
}
}
This public .insert() method first checks if there is a root node already created -- if not, it creates one and adds the data to it. Otherwise, it calls a second, overloaded, .insert() method, which is recursive in nature. Why? You'll see in a moment:
/** HELPER METHOD
* Recursively adds data to the tree
*
* @param data to be added
* @param node the root node
* @return new node recursively
*/
private Node insert(T data, Node node) {
// create new root node, if it's not already created
if (node == null) {
node = new Node(data);
}
// Where does this data need to go?
if (data < node.data) {
// recursive call - passing the left child Node
// (effectively traversing left)
node.leftChild = insert(data, node.leftChild);
}
else if (data > node.data){
// recursive call - passing the right child Node
// (effectively traversing right)
node.rightChild = insert(data, node.rightChild);
}
// If you get here, you've either found duplicate data
// Or the other recursive calls are done.
// Either case, you can return this node
return node;
}
This private recursive method first checks if you are inserting data into a null node. If so, it creates a new Node object with the data provided.
It then checks to see if data is less than or greater than the data in node.
- If it's less, it tries to insert the data in the left child subtree.
- If it's greater, it tries to insert the data it in the right child subtree.
- If it's equal (neither less nor greater), then there's no need to do anything -- it's a duplicate, or it's the node you just created. In either case, you can return the current node, which connects to the tree as the recursive calls unwind.
So why use an overloaded recursive .insert() method? There are three reasons:
-
The nature of a binary search tree lends itself well to recursive methods. Remember that each node in a tree is also the root of another tree, called a subtree. This means you can treat each node the same because their structures are the same.
-
The first
publicnon-recursive method actually does some filtering for you. If the tree is empty, then there is no need to look at all the nodes in the tree at all. You create a newrootnode and populate it. -
The user of your tree doesn't need to know the specifics of how to work with the tree. They just want to add data to the tree and shouldn't need to specify the root of the tree. The non-recursive
publicmethod enables this, leaving the details of the recursion and returningNode<>objects to theprivaterecursive method.
Now that you've added data to the tree, you should know how to find it again.
Binary Tree Traversals
You can output every piece of data in a BST using a full traversal. Since BSTs sort the data as it's stored, you can quickly output the sorted data using a technique called an in-order traversal:
/**
* Traverses a BST in order
* No return -- this prints each item in the BST
*/
public void traverse(){
if (this.root!=null)
traverse(root);
}
/** HELPER METHOD
* Recursively traverse a BST in order
* @param node The root of the subtree to traverse
*/
private void traverse(Node<T> node) {
if (node != null){
traverse(node.leftChild);
System.out.println(node.data);
traverse(node.rightChild);
}
}
By now, the use of a public method and a private recursive method should be familiar. The real work occurs in the private method, which first checks to see if the node passed in is null. If not, then the method traverses the left sub-tree before printing the current data item. It then traverses the right sub-tree. But why?
Remember that all the data down the left sub2-tree is less than whatever the current node stores, and the right sub-tree contains data that is greater than the current node. This property is true for every node in the BST. Therefore, by printing everything from the left sub-tree first, then the current node's data, and then the right sub-tree, you print everything in sorted order.
There are also traversals called pre-order and post-order, where the current node's data is output either before or after the sub-trees, respectively. These traversals have limited practical use with binary search trees but are useful for other types of trees. Implementing these is left as a lab.
Delete Data
By now, you may expect that deleting data from a BST requires two overloaded methods. Please consider your expectations met:
/**
* Delete a piece of data from the tree, if it exists
* @param data The data item to delete
*/
public void delete(T data) {
if (this.root != null)
this.root = delete(this.root, data);
}
/** HELPER METHOD
* Recursively removes a piece of data from the tree, if it exists
*
* @param node The subtree to explore for the data
* @param data The data item to remove
* @return The new subtree with the data item removed
*/
private Node<T> delete(Node<T> node, T data) {
// If this node is null, you don't have to look anywhere
if (node == null) return null;
* No return -- this prints each item in the BST
// Is the data less than the current node? Go left
if (data.compareTo(node.data) < 0) {
node.leftChild = delete(node.leftChild, data);
}
// Is the data greater than the current node? Go right
else if (data.compareTo(node.data) > 0) {
node.rightChild = delete(node.rightChild, data);
}
// Is this the node you want to remove
else if (data.compareTo(node.data) == 0){
// How many children does this node have?
// Zero children -- just remove the node
if (node.leftChild == null && node.rightChild == null){
return null;
}
// One child only? move the other child up
else if (node.leftChild == null) {
return node.rightChild;
}
else if (node.rightChild == null) {
return node.leftChild;
}
// You have two children -- find the node to move up
else {
// Find the smallest node which is bigger than the left
// This is left most node down the right branch
Node<T> smallest = node.rightChild;
while (smallest.leftChild != null){
smallest = smallest.leftChild;
}
// Swap the current node's data with the smallest node
T swap = node.data;
node.data = smallest.data;
smallest.data = swap;
*
node.rightChild = delete(node.rightChild, data);
}
}
return node;
}
Like deleting data from a linked list, deleting data from a BST involves reassigning references to remove nodes from the tree. This is more complicated in a tree because each node can have zero, one, or two references. Simply reassigning a leftChild or rightChild may remove more of the tree than expected.
When you have found the node you want to remove, you need to figure out how many children it has so you can do the right thing:
- If the node has no children, it's called a leaf node. Since it has no children, you can simply remove it by returning
null. - If the node has a single child, you can remove it by returning the existing child. This is similar to the linked list case, where you skip over a node using
node.next.next. - If the node has two children, you can't just bypass it. You need to find a node which can replace it.
You can see how this works with a diagram - consider the following tree:
[Binary Search Tree](images/tree before delete.png)
You want to delete the node labeled 31, which has two children. You must find another node to replace it that satisfies the requirements of the BST. Because you are working with the sub-tree starting at 31, your choices are limited to the children of that sub-tree. So, how do you find another node to replace 31?
In fact, there are two such nodes:
- Find the largest node in the left sub-tree, which is the largest number smaller than 31 (in this case, 28).
- Find the smallest node in the right sub-tree, which is the smallest number larger than 31 (in this case, 39).
You do this by either:
- Starting with the left sub-tree, follow the
rightChildlinks until you hit anull. - Starting with the right sub-tree, follow the
leftChildlinks until you hit anull.
The sample code follows the second path, starting with the right sub-tree and finding the smallest item in that tree. It swaps that value with the current node and then continues to search for and delete that node. Implementing the other path is left as a lab for the student.
If you'd like to continue learning about Trees in Java, check out the following resources in the Java 301 course:
Summary: Binary Search Tree Operations
This section covered how to insert, delete, search, and list all the data in a binary search tree in Java. You learned how to start from the root of a tree and, through recursion, add data to a tree, as well as find data in a tree. You learned some of the challenges of removing data from a tree and how to address them. You also learned how to traverse a tree to retrieve all the data in the tree.