Insertion in binary search tree (BST) in Java

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.

Insertion in a binary search tree

To insert a value in a BST:

Add the specified value to a new node.
Make the new node the root if the tree is empty.
Otherwise, begin at the base and work our way up the tree using the guidelines below:
- Go to the left subtree if the value is smaller than the value of the current node.
- Go to the right subtree if the value is higher than the value of the current node.
- This approach should be repeated until a suitable opening is discovered.
Place the new node in the vacant space.

Code example

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);
  }
}

Explanation

Let’s understand the above code implementation:

Lines 1–9: We define the Node class, which stands for a binary tree node.
- Line 2: We define an integer data to store the value of the node.
- Line 3: We declare two references of type Node with the names left and right to link the current node’s left and right child nodes, respectively.
- Lines 5–7: We define the 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.
Lines 11–35: We define a class named BST.
- Line 12: We declare a Node variable named root.
- Lines 14–16: We define the BST class constructor and set the root variable to null to represent an empty tree.
- Lines 18–20: We define the 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.
- Lines 22–35: We define the 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.
- Lines 37–43: We define the 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.
Line 48: We create an instance named tree of the BST class.
Lines 49–55: We insert several values into the tree using the insertValue() method.
Lines 57–58: We call the printTree() method on the tree object, passing the root of the tree to print its elements in the in-order traversal.

Free Resources