# How to insert a Node in a Binary Search Tree

**Recommended to visit before going through this article:**

**What is a Binary Search Tree? How to represent it ? And, related terminologies…**

Inserting a node in a given Binary Search Tree is a process to add a new node; let’s say if **node A** has to be inserted then you got to follow below steps –

**STEP 1:** **If there is no node in a given BST** then insert **node A** as its Root Node.

**STEP 2:** Find the Node in a given Binary Search Tree where we need to insert A ( as either left or a right child ). To find so, just compare the value of **node A** with the root node’s value:

**if node A has a value greater than the root node’s value** – traverse down the root node in its right node and Go to Step 2 by considering this right node as the root node (Note: if there is no right node straight go to Step 3)

**if node A has a value lesser than the root node’s value** – traverse down the root node in its left node and Go to Step 2 by considering this left node as the root node (Note: if there is no left node straight go to Step 3)

**STEP 3:** Once the Node is found using step 1:

**if value of node A is greater than this Node’s value** – insert A as the right child of this node

**if value of node A is lesser than this Node’s value** – insert A as the left child of this node

**Above Algorithm can be implemented using two popular ways – Recursive and an Iterative way**

**BST,java**

package org.gontuseries.bst; public class BST { private Node root; public void insert(int value) { root = insert(value, root); } private Node insert(int value, Node currentNode) { if (currentNode == null) { return createNewNode(value); } if (value > currentNode.getValue()) { currentNode = insert(value, currentNode.getRightNode()); } else if (value < currentNode.getValue()) { currentNode = insert(value, currentNode.getLeftNode()); } else { System.out.println("Node with the same value already exists in the BST"); } return currentNode; } private Node createNewNode(int value) { Node node = new Node(value); return node; } }

package org.gontuseries.bst; public class BST { private Node root; private void insert(int value) { if (root == null) root = createNewNode(value); else { Node currentNode = root; while (true) { if (value > currentNode.getValue()) { if (currentNode.getRightNode() != null) { currentNode = currentNode.getRightNode(); } else { currentNode.setRightNode(createNewNode(value)); } } else if (value < currentNode.getValue()) { if (currentNode.getLeftNode() != null) { currentNode = currentNode.getLeftNode(); } else { currentNode.setLeftNode(createNewNode(value)); } } else { System.out.println("Node with the same value already exists in the BST"); } } } } private Node createNewNode(int value) { Node node = new Node(value); return node; } }

**Node.java**

package org.gontuseries.bst; public class Node { Node(int value) { this.value = value; this.leftNode = null; this.rightNode = null; } private int value; private Node leftNode; private Node rightNode; // --- writing all getters and setters for all properties //i.e for value, leftNode, rightNode }

**Time Complexity:** The run time complexity of insert operation using Recursive way is: O(height of a Binary Search Tree) **i.e O(h) [worst-case]**

a) In case of a skewed Binary Search Tree the height is equal to the number of nodes in it; so, it becomes O(**n)[worst-case]**

b) In case of a Binary Search Tree built using some Tree Balancing Techniques like AVL, RED Black etc the height is equal to log (number of nodes in it); so it becomes **log(n) [worst-case]**

where, ‘n’ is the number of nodes in a binary search tree.