Binary Search Tree Insertion Method in Java, explain it and give me a code example
A Binary Search Tree (BST) is a data structure that maintains sorted order of elements, allowing for efficient insertion, deletion, and lookup operations. In a BST, each node has at most two children, and for any given node:
The insertion method for a BST involves the following steps:
Here is a simple implementation of a Binary Search Tree in Java, including the insertion method:
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
private TreeNode root;
public BinarySearchTree() {
this.root = null;
}
// Public method to insert a value
public void insert(int value) {
root = insertRec(root, value);
}
// Recursive method to insert a value
private TreeNode insertRec(TreeNode node, int value) {
// If the current node is null, create a new node
if (node == null) {
return new TreeNode(value);
}
// Otherwise, recur down the tree
if (value < node.value) {
node.left = insertRec(node.left, value);
} else if (value > node.value) {
node.right = insertRec(node.right, value);
}
// Return the unchanged node pointer
return node;
}
// In-order traversal to display the tree
public void inorder() {
inorderRec(root);
}
private void inorderRec(TreeNode node) {
if (node != null) {
inorderRec(node.left);
System.out.print(node.value + " ");
inorderRec(node.right);
}
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
System.out.println("In-order traversal of the BST:");
bst.inorder(); // Output: 20 30 40 50 60 70 80
}
}
insert
method is a public method that starts the insertion process.insertRec
method is a private recursive method that handles the actual insertion logic.inorder
method prints the values of the BST in sorted order by recursively visiting the left child, the current node, and then the right child.This implementation provides a basic structure for a Binary Search Tree and can be expanded with additional features such as deletion, searching, and balancing.