...

/

Insert Values in a Binary Search Tree

Insert Values in a Binary Search Tree

This lesson will help you learn recursion through trees.

What is a Binary Search Tree?

A Binary Search Tree (BST) is a hierarchical data structure that consists of vertices connected through edges. The value of the left node is less than the value of the parent node, and the value of the right node is greater than the value of the parent node.

%0 node_1 6 node_1553672885624 4 node_1->node_1553672885624 node_3 8 node_1->node_3 node_1553672900128 2 node_1553672885624->node_1553672900128 node_1553673153245 5 node_1553672885624->node_1553673153245

Code Implementation

Press + to interact
class binarySearchTree {
//Variables
private Node root;
//Getter for Root
public Node getRoot() {
return root;
}
//Setter for root
public void setRoot(Node root) {
this.root = root;
}
//Recursive function to insert a value in BST
public Node recursive_insert(Node currentNode, int value) {
//Base Case
if (currentNode == null) {
return new Node(value);
}
if (value < currentNode.getData()) {
//Iterate left sub-tree
currentNode.setLeftChild(recursive_insert(currentNode.getLeftChild(), value));
} else if (value > currentNode.getData()) {
//Iterate right sub-tree
currentNode.setRightChild(recursive_insert(currentNode.getRightChild(), value));
} else {
// value already exists
return currentNode;
}
return currentNode;
}
//Function to call recursive insert
public boolean insert(int value) {
root = recursive_insert(this.root, value);
return true;
}
//Function to check if Tree is empty or not
public boolean isEmpty() {
return root == null; //if root is null then it means Tree is empty
}
//Just for Testing purpose
public void printTree(Node current) {
if (current == null) return;
System.out.print(current.getData() + ",");
printTree(current.getLeftChild());
printTree(current.getRightChild());
}
public static void main(String args[]) {
binarySearchTree bsT = new binarySearchTree();
bsT.insert(6);
bsT.insert(4);
bsT.insert(8);
bsT.insert(5);
bsT.insert(2);
bsT.insert(8);
bsT.insert(12);
bsT.insert(10);
bsT.insert(14);
bsT.printTree(bsT.getRoot());
}
}

Understanding the Code

In the code above, the function insert is a recursive method, since it makes a recursive call. Below is an explanation of the above code:

Driver Method

  • In the main code, we create a new BST, named bsT.

  • The insert() method is ...