Java Binary Search Tree Implementation
Chapter:
Miscellaneous
Last Updated:
21-03-2023 17:36:40 UTC
Program:
/* ............... START ............... */
public class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinarySearchTree {
Node root;
public BinarySearchTree() {
root = null;
}
public void insert(int data) {
root = insertRec(root, data);
}
public Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
public Node search(Node root, int data) {
if (root == null || root.data == data) {
return root;
}
if (data < root.data) {
return search(root.left, data);
}
return search(root.right, data);
}
public void inorderTraversal() {
inorderRec(root);
}
public void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal:");
tree.inorderTraversal();
System.out.println("\nSearching for 40:");
Node result = tree.search(tree.root, 40);
if (result != null) {
System.out.println("Found " + result.data);
} else {
System.out.println("Not found");
}
}
}
/* ............... END ............... */
Output
Inorder traversal:
20 30 40 50 60 70 80
Searching for 40:
Found 40
Notes:
-
The program defines two classes - Node and BinarySearchTree. The Node class represents a node in the BST with an integer value, and two child nodes - left and right, which can also be null indicating the absence of a child node. The BinarySearchTree class defines the BST data structure with a root node, which can be null indicating an empty tree.
- The BinarySearchTree class has several methods for operations on the BST. The insert(int data) method is used to insert a new node with the given data value into the BST by calling the recursive insertRec(Node root, int data) method. This method traverses the tree recursively, starting from the root node, to find the appropriate location to insert the new node based on its value.
- The search(Node root, int data) method is used to search for a node with the given data value in the BST rooted at the specified root node. This method also traverses the tree recursively to find the node with the matching value.
- Finally, the inorderTraversal() method is used to traverse the BST in order and print the values of the nodes. The inorderRec(Node root) method is a recursive helper method for the traversal.
- In the main() method, a BinarySearchTree object is created, and some nodes are inserted into the BST using the insert() method. The inorderTraversal() method is then called to print the values of the nodes in the BST. Finally, the search() method is called to search for a node with a value of 40, and the result is printed.
Tags
# Java binary search tree library # Java Binary Search Tree Implementation # How to create a binary search tree