This blog teaches you how to use trees and binary search trees in Java, covering the concepts, implementation, and traversal methods with examples.
1. Introduction
In this blog, you will learn how to use trees and binary search trees to organize and search data hierarchically in Java. Trees are one of the most important and versatile data structures in computer science. They can be used to model various real-world problems, such as file systems, XML documents, arithmetic expressions, and decision making.
Binary search trees are a special kind of trees that allow fast and efficient search, insertion, and deletion operations. They are widely used to implement dictionaries, maps, sets, and other abstract data types. Binary search trees also have applications in sorting, searching, and compression algorithms.
By the end of this blog, you will be able to:
- Define and explain the concepts and properties of trees and binary search trees.
- Implement trees and binary search trees in Java using object-oriented programming.
- Traverse trees and binary search trees in different ways using recursion.
- Perform common operations on binary search trees, such as insertion, deletion, and search.
Are you ready to dive into the world of trees and binary search trees? Let’s get started!
2. What are Trees?
A tree is a data structure that consists of a set of nodes connected by edges. A tree can be seen as a hierarchical representation of data, where each node can have zero or more child nodes. A tree can also be seen as a special kind of graph, where there is exactly one path between any two nodes.
The most common way to visualize a tree is to draw it as an inverted tree, where the root node is at the top and the child nodes are below it. For example, the following figure shows a tree with seven nodes and six edges.
Trees are widely used in computer science because they can model many real-world problems, such as file systems, XML documents, arithmetic expressions, and decision making. Trees can also support efficient search, insertion, and deletion operations, as well as various traversal methods.
But what are the basic concepts and properties of trees? How can we classify different types of trees? And how can we implement trees in Java? In the next sections, we will answer these questions and more.
2.1. Terminology and Properties
Before we dive into the implementation and traversal of trees, let’s first review some basic terminology and properties of trees. Understanding these concepts will help you to work with trees more effectively and efficiently.
A tree is a data structure that consists of a set of nodes connected by edges. A node is a unit of data that can have zero or more child nodes. An edge is a link that connects a parent node to a child node. A tree can also be seen as a special kind of graph, where there is exactly one path between any two nodes.
Here are some important terms and properties of trees:
- The root is the node that has no parent. It is the topmost node of the tree. There can be only one root in a tree.
- The height of a node is the number of edges in the longest path from the node to a leaf. A leaf is a node that has no children. The height of a tree is the height of its root.
- The depth of a node is the number of edges in the path from the node to the root. The depth of the root is zero.
- The level of a node is the depth of the node plus one. The level of the root is one.
- The degree of a node is the number of children it has. The degree of a tree is the maximum degree of any node in the tree.
- The size of a tree is the number of nodes it contains.
- A subtree of a tree is a tree that consists of a node and all its descendants. A subtree is also a tree by itself.
- A path in a tree is a sequence of nodes that are connected by edges. A path can also be represented by a sequence of edge labels.
- A binary tree is a tree where each node can have at most two children. A binary tree can also be seen as a tree where each node has a left child and a right child, which can be null.
Can you think of some examples of trees in real life or in computer science? How would you represent them using nodes and edges? Try to draw some trees and label their nodes with their heights, depths, levels, and degrees.
2.2. Types of Trees
Not all trees are the same. Depending on the structure and constraints of the nodes and edges, there are different types of trees that have different properties and applications. In this section, we will introduce some common types of trees and their characteristics.
One of the most basic types of trees is the binary tree, which we have already mentioned in the previous section. A binary tree is a tree where each node can have at most two children, which are called the left child and the right child. A binary tree can also be seen as a tree where each node has a left child and a right child, which can be null. For example, the following figure shows a binary tree with seven nodes.
A binary tree with seven nodes (source: Wikipedia)
Binary trees are widely used in computer science because they can support efficient search, insertion, and deletion operations, as well as various traversal methods. Binary trees also have many subtypes, such as binary search trees, which we will discuss in detail in the later sections.
Another common type of trees is the m-ary tree, which is a generalization of the binary tree. An m-ary tree is a tree where each node can have at most m children, where m is a fixed positive integer.
M-ary trees are useful for representing data that have more than two branches or choices, such as game trees, decision trees, and trie data structures. M-ary trees can also be traversed in different ways, such as level-order traversal, which we will cover in the later sections.
A special case of the m-ary tree is the n-ary tree, which is a tree where each node can have any number of children, without any limit. An n-ary tree can also be seen as a tree where each node has a list of children, which can be empty.
N-ary trees are often used to model hierarchical data, such as file systems, XML documents, and organizational charts. N-ary trees can also be converted into binary trees using various methods, such as the left-child right-sibling representation.
These are some of the common types of trees that you will encounter in computer science. There are also other types of trees, such as balanced trees, self-adjusting trees, and B-trees, which have different properties and applications. You can learn more about them from the links provided in the references section.
Can you identify the type of tree for each of the following examples? How would you implement them in Java? Try to write some code snippets to create and manipulate these trees.
- A family tree that shows the ancestors and descendants of a person.
- A Huffman tree that is used for data compression.
- A syntax tree that is used for parsing and evaluating expressions.
3. How to Implement Trees in Java
Now that you have learned some basic concepts and types of trees, let’s see how you can implement them in Java. There are different ways to implement trees in Java, but one of the most common and simple ways is to use object-oriented programming. In this section, we will show you how to create a generic Node class and a generic Tree class that can be used to represent any type of tree.
The first step is to create a Node class that represents a single node in a tree. A node has two main attributes: a data value and a list of children. The data value can be any type of object, such as an integer, a string, or a custom class. The list of children can be implemented using an array, an array list, or a linked list. For simplicity, we will use an array list in this example. Here is the code for the Node class:
// A generic Node class that represents a single node in a tree
public class Node {
// The data value of the node
private T data;
// The list of children of the node
private ArrayList<Node> children;
// A constructor that creates a node with a given data value
public Node(T data) {
this.data = data;
this.children = new ArrayList<>();
}
// A method that returns the data value of the node
public T getData() {
return data;
}
// A method that sets the data value of the node
public void setData(T data) {
this.data = data;
}
// A method that returns the list of children of the node
public ArrayList<Node> getChildren() {
return children;
}
// A method that adds a child node to the node
public void addChild(Node child) {
children.add(child);
}
// A method that removes a child node from the node
public void removeChild(Node child) {
children.remove(child);
}
}
The next step is to create a Tree class that represents a whole tree. A tree has one main attribute: the root node. The root node can be any type of node, as long as it matches the generic type of the tree. Here is the code for the Tree class:
// A generic Tree class that represents a whole tree
public class Tree {
// The root node of the tree
private Node root;
// A constructor that creates a tree with a given root node
public Tree(Node root) {
this.root = root;
}
// A method that returns the root node of the tree
public Node getRoot() {
return root;
}
// A method that sets the root node of the tree
public void setRoot(Node root) {
this.root = root;
}
}
With these two classes, you can create and manipulate any type of tree in Java. For example, you can create a binary tree of integers as follows:
// Create a binary tree of integers Tree tree = new Tree<>(new Node<>(1)); // Create the root node with value 1 Node root = tree.getRoot(); // Get the root node root.addChild(new Node<>(2)); // Add a left child node with value 2 root.addChild(new Node<>(3)); // Add a right child node with value 3 Node left = root.getChildren().get(0); // Get the left child node Node right = root.getChildren().get(1); // Get the right child node left.addChild(new Node<>(4)); // Add a left child node with value 4 left.addChild(new Node<>(5)); // Add a right child node with value 5 right.addChild(new Node<>(6)); // Add a left child node with value 6 right.addChild(new Node<>(7)); // Add a right child node with value 7
You can also create an n-ary tree of strings as follows:
// Create an n-ary tree of strings
Tree tree = new Tree<>(new Node<>("A")); // Create the root node with value "A"
Node root = tree.getRoot(); // Get the root node
root.addChild(new Node<>("B")); // Add a child node with value "B"
root.addChild(new Node<>("C")); // Add a child node with value "C"
root.addChild(new Node<>("D")); // Add a child node with value "D"
Node b = root.getChildren().get(0); // Get the first child node
Node c = root.getChildren().get(1); // Get the second child node
Node d = root.getChildren().get(2); // Get the third child node
b.addChild(new Node<>("E")); // Add a child node with value "E"
b.addChild(new Node<>("F")); // Add a child node with value "F"
c.addChild(new Node<>("G")); // Add a child node with value "G"
d.addChild(new Node<>("H")); // Add a child node with value "H"
d.addChild(new Node<>("I")); // Add a child node with value "I"
d.addChild(new Node<>("J")); // Add a child node with value "J"
As you can see, the Node and Tree classes are very flexible and can be used to represent any type of tree in Java. However, they are also very generic and do not have any specific methods or properties for different types of trees. For example, they do not have any methods for searching, inserting, or deleting nodes in a binary search tree. In the next sections, we will show you how to create a subclass of the Tree class that implements the specific features of a binary search tree.
3.1. Node Class
In the previous section, we showed you how to create a generic Node class that can be used to represent any type of node in a tree. However, if we want to implement a binary search tree, we need to modify the Node class slightly. A binary search tree is a special kind of binary tree where the nodes are ordered according to a certain property. This property is that for any node, the value of its left child is less than or equal to its value, and the value of its right child is greater than or equal to its value. This property allows us to perform efficient search, insertion, and deletion operations on a binary search tree.
To implement a binary search tree, we need to change the Node class in two ways. First, we need to restrict the type of the data value to be comparable, such as an integer, a string, or a custom class that implements the Comparable interface. This is because we need to compare the values of the nodes to maintain the order property of the binary search tree. Second, we need to change the list of children to be two specific children: the left child and the right child. This is because a binary search tree is a binary tree, and each node can have at most two children. Here is the code for the modified Node class:
// A generic Node class that represents a single node in a binary search tree
public class Node> {
// The data value of the node
private T data;
// The left child of the node
private Node left;
// The right child of the node
private Node right;
// A constructor that creates a node with a given data value
public Node(T data) {
this.data = data;
this.left = null;
this.right = null;
}
// A method that returns the data value of the node
public T getData() {
return data;
}
// A method that sets the data value of the node
public void setData(T data) {
this.data = data;
}
// A method that returns the left child of the node
public Node getLeft() {
return left;
}
// A method that sets the left child of the node
public void setLeft(Node left) {
this.left = left;
}
// A method that returns the right child of the node
public Node getRight() {
return right;
}
// A method that sets the right child of the node
public void setRight(Node right) {
this.right = right;
}
}
As you can see, the modified Node class is very similar to the generic Node class, except for the type restriction and the change of the children attribute. With this class, you can create and manipulate nodes in a binary search tree. For example, you can create a binary search tree of integers as follows:
// Create a binary search tree of integers Node root = new Node<>(5); // Create the root node with value 5 root.setLeft(new Node<>(3)); // Set the left child of the root node with value 3 root.setRight(new Node<>(7)); // Set the right child of the root node with value 7 Node left = root.getLeft(); // Get the left child of the root node Node right = root.getRight(); // Get the right child of the root node left.setLeft(new Node<>(2)); // Set the left child of the left node with value 2 left.setRight(new Node<>(4)); // Set the right child of the left node with value 4 right.setLeft(new Node<>(6)); // Set the left child of the right node with value 6 right.setRight(new Node<>(8)); // Set the right child of the right node with value 8
In the next section, we will show you how to create a subclass of the Tree class that implements the specific features of a binary search tree.
3.2. Tree Class
Now that we have defined the Node class, we can create the Tree class that will represent the entire tree structure. The Tree class will have two attributes: a root node and a size that indicates the number of nodes in the tree. The Tree class will also have several methods to perform various operations on the tree, such as adding, removing, and finding nodes.
The constructor of the Tree class will take a root node as an argument and initialize the size to 1. If the root node is null, the size will be 0. The constructor will also check if the root node has any children and update the size accordingly. Here is the code for the constructor:
public class Tree {
// Attributes
private Node root;
private int size;
// Constructor
public Tree(Node root) {
this.root = root;
if (root == null) {
size = 0;
} else {
size = 1;
size += countChildren(root); // Helper method to count the children of a node
}
}
The countChildren method is a helper method that takes a node as an argument and returns the number of its children. It uses a recursion technique to traverse the subtree rooted at the given node and count the nodes along the way. Here is the code for the countChildren method:
// Helper method to count the children of a node
private int countChildren(Node node) {
if (node == null) {
return 0;
}
int count = 0;
for (Node child : node.getChildren()) {
count++;
count += countChildren(child); // Recursive call
}
return count;
}
The Tree class will also have getter and setter methods for the root and size attributes, as well as a toString method that returns a string representation of the tree. Here is the code for these methods:
// Getter and setter methods
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
// toString method
public String toString() {
return "Tree [root=" + root + ", size=" + size + "]";
}
In the next section, we will see how to add, remove, and find nodes in the tree using the Tree class methods.
4. How to Traverse Trees in Java
One of the most important and useful operations on trees is traversal. Traversal is the process of visiting each node in the tree exactly once and performing some action on it, such as printing its value, updating its data, or checking a condition. Traversal can also be used to search for a specific node or value in the tree.
There are different ways to traverse a tree, depending on the order in which we visit the nodes. The most common traversal methods are depth-first traversal and breadth-first traversal. In depth-first traversal, we explore the depth of the tree before the breadth, meaning we visit the children of a node before its siblings. In breadth-first traversal, we explore the breadth of the tree before the depth, meaning we visit the siblings of a node before its children.
Both depth-first and breadth-first traversal can be implemented using recursion or iteration. Recursion is a technique where a method calls itself to solve a smaller subproblem. Iteration is a technique where a loop is used to repeat a set of instructions until a condition is met. Both techniques have their advantages and disadvantages, depending on the size and shape of the tree, the memory usage, and the readability of the code.
In the next sections, we will see how to implement depth-first and breadth-first traversal in Java using both recursion and iteration. We will also see how to apply these traversal methods to different types of trees, such as binary trees and binary search trees.
4.1. Depth-First Traversal
In this section, you will learn how to implement depth-first traversal in Java. Depth-first traversal is a method of visiting each node in a tree exactly once by exploring the depth of the tree before the breadth. This means that you visit the children of a node before its siblings.
There are three main types of depth-first traversal: pre-order, in-order, and post-order. The difference between them is the order in which you visit the root, left, and right nodes of a subtree. Here is a summary of the three types:
- Pre-order: visit the root node first, then the left subtree, then the right subtree.
- In-order: visit the left subtree first, then the root node, then the right subtree.
- Post-order: visit the left subtree first, then the right subtree, then the root node.
Depth-first traversal can be implemented using either recursion or iteration. Recursion is a technique where a method calls itself to solve a smaller subproblem. Iteration is a technique where a loop is used to repeat a set of instructions until a condition is met. Both techniques have their advantages and disadvantages, depending on the size and shape of the tree, the memory usage, and the readability of the code.
In the next subsections, we will see how to implement pre-order, in-order, and post-order traversal in Java using both recursion and iteration. We will also see how to apply these traversal methods to different types of trees, such as binary trees and binary search trees.
4.2. Breadth-First Traversal
In this section, you will learn how to implement breadth-first traversal in Java. Breadth-first traversal is a method of visiting each node in a tree exactly once by exploring the breadth of the tree before the depth. This means that you visit the siblings of a node before its children.
Breadth-first traversal is also known as level-order traversal, because it visits the nodes in each level of the tree from left to right. For example, the following figure shows the order of nodes visited in breadth-first traversal for the same binary tree as in the previous section.
The order of nodes visited in breadth-first traversal for a binary tree (source: Baeldung)
Breadth-first traversal can be implemented using iteration with the help of a queue. A queue is a data structure that follows the first-in first-out (FIFO) principle, meaning that the first element added to the queue is the first one to be removed. A queue can be used to store the nodes that are waiting to be visited in breadth-first traversal.
The algorithm for breadth-first traversal using iteration and a queue is as follows:
- Create an empty queue and add the root node to it.
- While the queue is not empty, do the following:
- Remove the first node from the queue and perform some action on it, such as printing its value.
- Add the left child of the node to the queue, if it exists.
- Add the right child of the node to the queue, if it exists.
- Repeat until the queue is empty.
In the next subsection, we will see how to implement this algorithm in Java using the LinkedList class, which implements the Queue interface. We will also see how to apply this traversal method to different types of trees, such as binary trees and binary search trees.
5. What are Binary Search Trees?
A binary search tree is a special kind of binary tree that satisfies the following property: for any node in the tree, the values of all the nodes in its left subtree are smaller than its value, and the values of all the nodes in its right subtree are larger than its value. This property makes binary search trees efficient for searching, inserting, and deleting data.
For example, the following figure shows a binary search tree with seven nodes. You can see that the value of each node is greater than the values of its left subtree and smaller than the values of its right subtree.
A binary search tree with seven nodes (source: Baeldung)
Binary search trees have many applications in computer science, such as implementing dictionaries, maps, sets, and other abstract data types. They can also be used to perform sorting, searching, and compression algorithms.
However, binary search trees are not always balanced, meaning that the height of the left and right subtrees may differ significantly. This can affect the performance of the operations on the tree, making them slower and less efficient. Therefore, there are different types of binary search trees that try to maintain a balanced structure, such as AVL trees, red-black trees, and splay trees.
In the next sections, you will learn how to perform common operations on binary search trees, such as insertion, deletion, and search. You will also learn how to implement binary search trees in Java using the BinarySearchTree class.
5.1. Definition and Characteristics
A binary search tree is a special kind of binary tree that satisfies the following property: for any node in the tree, the values of all the nodes in its left subtree are smaller than its value, and the values of all the nodes in its right subtree are larger than its value. This property makes binary search trees efficient for searching, inserting, and deleting data.
For example, the following figure shows a binary search tree with seven nodes. You can see that the value of each node is greater than the values of its left subtree and smaller than the values of its right subtree.
A binary search tree with seven nodes (source: Baeldung)
Binary search trees have many applications in computer science, such as implementing dictionaries, maps, sets, and other abstract data types. They can also be used to perform sorting, searching, and compression algorithms.
However, binary search trees are not always balanced, meaning that the height of the left and right subtrees may differ significantly. This can affect the performance of the operations on the tree, making them slower and less efficient. Therefore, there are different types of binary search trees that try to maintain a balanced structure, such as AVL trees, red-black trees, and splay trees.
In the next sections, you will learn how to perform common operations on binary search trees, such as insertion, deletion, and search. You will also learn how to implement binary search trees in Java using the BinarySearchTree class.
5.2. Operations on Binary Search Trees
In this section, you will learn how to perform common operations on binary search trees, such as insertion, deletion, and search. These operations are based on the property that for any node in the tree, the values of all the nodes in its left subtree are smaller than its value, and the values of all the nodes in its right subtree are larger than its value.
The insertion operation adds a new node to the binary search tree in the correct position, maintaining the binary search tree property. The algorithm for insertion is as follows:
- Start from the root node and compare the value of the new node with the value of the current node.
- If the value of the new node is smaller than the value of the current node, go to the left child of the current node. If the left child is null, insert the new node as the left child and return.
- If the value of the new node is larger than the value of the current node, go to the right child of the current node. If the right child is null, insert the new node as the right child and return.
- Repeat steps 2 and 3 until the new node is inserted or the tree is traversed.
The deletion operation removes a node from the binary search tree and adjusts the tree structure accordingly. The algorithm for deletion is as follows:
- Find the node to be deleted by using the search operation. If the node is not found, return.
- If the node to be deleted has no children, simply remove it from the tree and return.
- If the node to be deleted has one child, replace it with its child and return.
- If the node to be deleted has two children, find the smallest node in its right subtree (the successor) and replace the node to be deleted with the successor. Then, delete the successor from its original position and return.
The search operation finds a node with a given value in the binary search tree and returns it. The algorithm for search is as follows:
- Start from the root node and compare the value of the node to be searched with the value of the current node.
- If the values are equal, return the current node.
- If the value of the node to be searched is smaller than the value of the current node, go to the left child of the current node and repeat step 2.
- If the value of the node to be searched is larger than the value of the current node, go to the right child of the current node and repeat step 2.
- If the tree is traversed and the node is not found, return null.
In the next section, you will see how to implement these operations in Java using the BinarySearchTree class.
6. How to Implement Binary Search Trees in Java
In this section, you will learn how to implement binary search trees in Java using the BinarySearchTree class. The BinarySearchTree class will extend the Tree class that we created in the previous section, and override some of its methods to suit the binary search tree property. The BinarySearchTree class will also have some additional methods to perform the operations of insertion, deletion, and search on the binary search tree.
The constructor of the BinarySearchTree class will take a root node as an argument and call the super constructor of the Tree class. It will also check if the root node satisfies the binary search tree property, and throw an exception if it does not. Here is the code for the constructor:
public class BinarySearchTree extends Tree {
// Constructor
public BinarySearchTree(Node root) {
super(root); // Call the super constructor of the Tree class
if (!isBST(root, null, null)) { // Check if the root node satisfies the binary search tree property
throw new IllegalArgumentException("The root node does not satisfy the binary search tree property");
}
}
The isBST method is a helper method that takes a node and two optional parameters, min and max, as arguments and returns a boolean value indicating whether the node satisfies the binary search tree property. It uses a recursion technique to traverse the subtree rooted at the given node and compare its value with the min and max values. Here is the code for the isBST method:
// Helper method to check if a node satisfies the binary search tree property
private boolean isBST(Node node, Integer min, Integer max) {
if (node == null) {
return true;
}
if (min != null && node.getValue() <= min) {
return false;
}
if (max != null && node.getValue() >= max) {
return false;
}
return isBST(node.getLeft(), min, node.getValue()) // Recursive call for the left subtree
&& isBST(node.getRight(), node.getValue(), max); // Recursive call for the right subtree
}
The BinarySearchTree class will also have methods to perform the operations of insertion, deletion, and search on the binary search tree. These methods will use the algorithms that we learned in the previous section, and update the size attribute of the tree accordingly. Here is the code for these methods:
// Method to insert a new node to the binary search tree
public void insert(int value) {
root = insert(root, value); // Call the helper method with the root node as the argument
size++; // Increment the size of the tree
}
// Helper method to insert a new node to the binary search tree
private Node insert(Node node, int value) {
if (node == null) {
return new Node(value); // Create a new node with the given value and return it
}
if (value < node.getValue()) {
node.setLeft(insert(node.getLeft(), value)); // Recursive call for the left subtree
} else if (value > node.getValue()) {
node.setRight(insert(node.getRight(), value)); // Recursive call for the right subtree
}
return node; // Return the updated node
}
// Method to delete a node from the binary search tree
public void delete(int value) {
root = delete(root, value); // Call the helper method with the root node as the argument
size--; // Decrement the size of the tree
}
// Helper method to delete a node from the binary search tree
private Node delete(Node node, int value) {
if (node == null) {
return null; // Return null if the node is not found
}
if (value < node.getValue()) {
node.setLeft(delete(node.getLeft(), value)); // Recursive call for the left subtree
} else if (value > node.getValue()) {
node.setRight(delete(node.getRight(), value)); // Recursive call for the right subtree
} else {
// Case 1: The node has no children
if (node.getLeft() == null && node.getRight() == null) {
return null; // Simply remove the node
}
// Case 2: The node has one child
if (node.getLeft() == null) {
return node.getRight(); // Replace the node with its right child
}
if (node.getRight() == null) {
return node.getLeft(); // Replace the node with its left child
}
// Case 3: The node has two children
Node successor = findMin(node.getRight()); // Find the smallest node in the right subtree (the successor)
node.setValue(successor.getValue()); // Replace the node's value with the successor's value
node.setRight(delete(node.getRight(), successor.getValue())); // Delete the successor from its original position
}
return node; // Return the updated node
}
// Helper method to find the smallest node in a subtree
private Node findMin(Node node) {
if (node == null) {
return null; // Return null if the node is null
}
while (node.getLeft() != null) {
node = node.getLeft(); // Go to the leftmost node
}
return node; // Return the smallest node
}
// Method to search for a node with a given value in the binary search tree
public Node search(int value) {
return search(root, value); // Call the helper method with the root node as the argument
}
// Helper method to search for a node with a given value in the binary search tree
private Node search(Node node, int value) {
if (node == null) {
return null; // Return null if the node is not found
}
if (value == node.getValue()) {
return node; // Return the node if the values are equal
}
if (value < node.getValue()) {
return search(node.getLeft(), value); // Recursive call for the left subtree
}
return search(node.getRight(), value); // Recursive call for the right subtree
}
In the next section, you will see how to use the BinarySearchTree class to create and manipulate binary search trees in Java.
6.1. Binary Search Tree Class
In this section, you will learn how to implement a binary search tree class in Java. A binary search tree is a special kind of tree that has the following properties:
- Each node has at most two child nodes, called the left child and the right child.
- The value of the left child is less than or equal to the value of the parent node.
- The value of the right child is greater than or equal to the value of the parent node.
- The left and right subtrees of any node are also binary search trees.
The following figure shows an example of a binary search tree with six nodes.
A binary search tree with six nodes (source: Wikipedia)
To implement a binary search tree class in Java, we need to define two classes: a Node class and a BST class. The Node class represents a single node in the tree, and it has three fields: value, left, and right. The BST class represents the whole tree, and it has one field: root, which is a reference to the root node of the tree.
The following code shows the basic structure of the Node and BST classes.
// Node class
class Node {
// value of the node
int value;
// left child of the node
Node left;
// right child of the node
Node right;
// constructor
public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// BST class
class BST {
// root of the tree
Node root;
// constructor
public BST() {
this.root = null;
}
}
In the next section, you will learn how to implement the common operations on binary search trees, such as insertion, deletion, and search.
6.2. Insertion, Deletion, and Search Methods
In this section, you will learn how to implement the common operations on binary search trees, such as insertion, deletion, and search. These operations are essential for manipulating and accessing the data stored in the tree. They also rely on the properties of binary search trees, such as the ordering of the values and the structure of the subtrees.
To insert a new node into a binary search tree, you need to find the appropriate position for it, according to its value. You start from the root node and compare the value of the new node with the value of the current node. If the new value is less than or equal to the current value, you move to the left child. If the new value is greater than the current value, you move to the right child. You repeat this process until you reach a null node, which means you have found the right place to insert the new node. You then create a new node with the given value and assign it as the left or right child of the previous node.
The following code shows how to implement the insertion method in the BST class.
// insertion method
public void insert(int value) {
// create a new node with the given value
Node newNode = new Node(value);
// if the tree is empty, set the new node as the root
if (root == null) {
root = newNode;
} else {
// otherwise, start from the root and find the right position for the new node
Node current = root;
Node parent = null;
while (true) {
// save the current node as the parent node
parent = current;
// if the new value is less than or equal to the current value, go to the left child
if (value <= current.value) {
current = current.left;
// if the left child is null, insert the new node there and return
if (current == null) {
parent.left = newNode;
return;
}
} else {
// if the new value is greater than the current value, go to the right child
current = current.right;
// if the right child is null, insert the new node there and return
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
}
To delete a node from a binary search tree, you need to find the node with the given value and remove it from the tree. You also need to handle three possible cases, depending on the number of children of the node to be deleted:
- If the node has no children, you simply set its parent’s reference to null.
- If the node has one child, you replace the node with its child and link it to its parent.
- If the node has two children, you find the minimum value in its right subtree and replace the node with that value. You then delete the minimum value node from the right subtree.
The following code shows how to implement the deletion method in the BST class.
// deletion method
public boolean delete(int value) {
// if the tree is empty, return false
if (root == null) {
return false;
}
// otherwise, start from the root and find the node to be deleted
Node current = root;
Node parent = null;
boolean isLeftChild = false;
while (current.value != value) {
// save the current node as the parent node
parent = current;
// if the value is less than the current value, go to the left child
if (value < current.value) {
current = current.left;
isLeftChild = true;
} else {
// if the value is greater than the current value, go to the right child
current = current.right;
isLeftChild = false;
}
// if the current node is null, the value is not found, return false
if (current == null) {
return false;
}
}
// at this point, the current node is the node to be deleted
// case 1: the node has no children
if (current.left == null && current.right == null) {
// if the node is the root, set the root to null
if (current == root) {
root = null;
} else {
// otherwise, set the parent's reference to null
if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
}
}
// case 2: the node has one child
else if (current.right == null) {
// if the node is the root, set the root to the left child
if (current == root) {
root = current.left;
} else {
// otherwise, replace the node with its left child and link it to its parent
if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
} else if (current.left == null) {
// if the node is the root, set the root to the right child
if (current == root) {
root = current.right;
} else {
// otherwise, replace the node with its right child and link it to its parent
if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
}
// case 3: the node has two children
else {
// find the minimum value in the right subtree of the node
Node min = getMin(current.right);
// replace the node's value with the minimum value
current.value = min.value;
// delete the minimum value node from the right subtree
deleteMin(current.right, min);
}
// return true if the deletion is successful
return true;
}
// helper method to find the minimum value node in a subtree
public Node getMin(Node node) {
// if the node is null, return null
if (node == null) {
return null;
}
// otherwise, go to the leftmost node
while (node.left != null) {
node = node.left;
}
// return the leftmost node
return node;
}
// helper method to delete the minimum value node from a subtree
public void deleteMin(Node node, Node min) {
// if the node is null, return
if (node == null) {
return;
}
// otherwise, start from the node and find the parent of the minimum value node
Node parent = null;
while (node != min) {
// save the node as the parent node
parent = node;
// go to the left child
node = node.left;
}
// at this point, the node is the minimum value node and the parent is its parent
// set the parent's left reference to the minimum value node's right reference
parent.left = min.right;
}
To search for a node in a binary search tree, you need to compare the value of the node with the value of the current node. You start from the root node and follow the same logic as the insertion method. If the value is less than or equal to the current value, you go to the left child. If the value is greater than the current value, you go to the right child. You repeat this process until you find the node with the same value or reach a null node, which means the value is not found.
The following code shows how to implement the search method in the BST class.
// search method
public boolean search(int value) {
// if the tree is empty, return false
if (root == null) {
return false;
}
// otherwise, start from the root and find the node with the given value
Node current = root;
while (current != null) {
// if the value is equal to the current value, return true
if (value == current.value) {
return true;
}
// if the value is less than the current value, go to the left child
else if (value < current.value) {
current = current.left;
}
// if the value is greater than the current value, go to the right child
else {
current = current.right;
}
}
// if the current node is null, the value is not found, return false
return false;
}
Now you have learned how to implement the basic operations on binary search trees in Java. In the next section, you will learn how to traverse binary search trees in different ways using recursion.
7. Conclusion
In this blog, you have learned how to use trees and binary search trees to organize and search data hierarchically in Java. You have covered the following topics:
- What are trees and what are their basic concepts and properties.
- What are the different types of trees and how to classify them.
- How to implement trees in Java using object-oriented programming.
- How to traverse trees in Java using different methods, such as depth-first and breadth-first traversal.
- What are binary search trees and what are their definition and characteristics.
- How to implement binary search trees in Java using the
NodeandBSTclasses. - How to perform common operations on binary search trees, such as insertion, deletion, and search.
Trees and binary search trees are powerful and versatile data structures that can help you solve many real-world problems. They can also improve the efficiency and performance of your algorithms and applications. By mastering the concepts and implementation of trees and binary search trees in Java, you can enhance your skills and knowledge as a programmer and a problem solver.
We hope you enjoyed this blog and learned something new and useful. If you have any questions or feedback, please feel free to leave a comment below. Thank you for reading and happy coding!
