Binary trees with a certain ordering attribute are called binary search trees (BSTs). In a BST, all nodes in a given node’s left subtree have values that are less than that node’s value, and all nodes in the node’s right subtree have values that are higher than that node’s value. Searching, insertion, and deletion operations may all be done effectively thanks to this ordering characteristic.
There are many applications that use BSTs for fast lookups and retrievals. Spell checkers, address lookup and packet forwarding in routers, game development, and data compression, all rely on BSTs.
Now, let’s focus on the insertion operation in a BST.
To insert a value in a BST:
left
subtree if the value is smaller than the value of the current node.right
subtree if the value is higher than the value of the current node.Here is the Java implementation of the insertion in the BST:
class Node {int data;Node left, right;public Node(int data) {this.data = data;left = right = null;}}class BST {Node root;public BST() {root = null;}public void insertValue(int data) {root = insertNode(root, data);}private Node insertNode(Node root, int data) {if (root == null) {root = new Node(data);return root;}if (data < root.data) {root.left = insertNode(root.left, data);} else if (data > root.data) {root.right = insertNode(root.right, data);}return root;}public void printTree(Node node) {if (node != null) {printTree(node.left);System.out.print(node.data + " ");printTree(node.right);}}}public class Main {public static void main(String[] args) {BST tree = new BST();tree.insertValue(50);tree.insertValue(30);tree.insertValue(20);tree.insertValue(40);tree.insertValue(70);tree.insertValue(60);tree.insertValue(80);System.out.println("In-order traversal of the BST:");tree.printTree(tree.root);}}
Let’s understand the above code implementation:
Node
class, which stands for a binary tree node.
data
to store the value of the node.Node
with the names left
and right
to link the current node’s left
and right
child nodes, respectively.Node
class constructor. In this constructor, we initialize the node with the value supplied as an integer parameter named data
. We set the left
and right
child references to null
.BST
.
Node
variable named root
.BST
class constructor and set the root
variable to null
to represent an empty tree.inserValue()
method for putting a new node with the specified value into the binary search tree. Inside this method, we call the insertNode()
method passing root
and data
variables.insertNode()
method that accepts two arguments: data
and root
. If the root
is null
, a new Node
is created with the given data and returned. If the data
is less than the current node’s data, the method recursively calls itself with the left child. If the data
is greater than the current node’s data, the method recursively calls itself with the right child. Lastly, the current node is returned.printTree()
method that performs an in-order traversal of the tree. In this method, If the current node is not null
, the method recursively calls itself with the left child, prints the data of the current node, and recursively calls itself with the right child.tree
of the BST
class.tree
using the insertValue()
method.printTree()
method on the tree
object, passing the root
of the tree to print its elements in the in-order traversal.Free Resources