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.
Code Implementation
Press + to interact
class binarySearchTree {//Variablesprivate Node root;//Getter for Rootpublic Node getRoot() {return root;}//Setter for rootpublic void setRoot(Node root) {this.root = root;}//Recursive function to insert a value in BSTpublic Node recursive_insert(Node currentNode, int value) {//Base Caseif (currentNode == null) {return new Node(value);}if (value < currentNode.getData()) {//Iterate left sub-treecurrentNode.setLeftChild(recursive_insert(currentNode.getLeftChild(), value));} else if (value > currentNode.getData()) {//Iterate right sub-treecurrentNode.setRightChild(recursive_insert(currentNode.getRightChild(), value));} else {// value already existsreturn currentNode;}return currentNode;}//Function to call recursive insertpublic boolean insert(int value) {root = recursive_insert(this.root, value);return true;}//Function to check if Tree is empty or notpublic boolean isEmpty() {return root == null; //if root is null then it means Tree is empty}//Just for Testing purposepublic 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, namedbsT
. -
The
insert()
method is ...