# Insert a Given Node in Binary Search Tree

Problem Statement: Given a root node reference of a Binary Search Tree and a key, insert a new node with value as the given key in the Binary Search Tree following the rules of a BST. Return the modified Binary Search Tree after insertion.

Examples

Example 1:

Input Format

Binary Search Tree: 4 2 7 1 3 -1 -1

Key to be Inserted: 5

Output

Modified Binary Search Tree: 4 2 7 1 3 5 -1

Or

Modified Binary Search Tree: 5 4 7 3 -1 -1 -1 1 3

Or

Modified Binary Search Tree: 4 2 5 1 3 -1 7

Explanation

After inserting a new node with value, there are multiple binary search trees possible. In the original binary search tree, the node with value 5 can be inserted as the left child of 7 or right child of 4 or can also become the root of the modified tree. These variations occur because there are multiple nodes with values that allow 5 to be inserted either on their left or right side, maintaining the Binary Search Tree properties.

Example 2:

Input Format:

Binary Search Tree: 6 3 8 2 4 7 -1

Key to be Inserted: 5

Output:

Modified Binary Search Tree: 6 3 8 2 4 7 -1 -1 -1 -1 5 -1 -1

Or

Modified Binary Search Tree: 6 5 8 3 -1 7 -1 3 2 -1 -1

Explanation

After inserting a new node with value, there are multiple binary search trees possible. In the original binary search tree, the node with value 5 can be inserted as the right child of 4 or left child of root 6. These variations occur because there are multiple nodes with values that allow 5 to be inserted either on their left or right side, maintaining the Binary Search Tree properties.

Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Algorithm:

Step 1: Traverse the tree to Determine the Insertion Point

Compare the value to be inserted with the current node’s value. If the value is less than the current node’s value, move to the left subtree. If the value is greater than the current node’s value, move to the right subtree. Repeat this process until finding a potential leaf (a null child) in the appropriate subtree.

Step 2: Insert a new node with the given value

Create a new node with the given value. Attach this new node as a child to the parent node at the empty spot found in the previous step. If the value is less than the parent’s node value, attach as the left child; otherwise, attach as the right child.

Step 3: Return the modified Binary Search Tree.

Code:

## C++ Code

#include <iostream>
using namespace std;

// Definition of TreeNode structure
// for a binary tree node
struct TreeNode {
// Value of the node
int val;

// Pointer to the left child node
TreeNode* left;
// Pointer to the right child node
TreeNode* right;

// Constructor to initialize the node with a
// value and set left and right pointers to null
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
// If the root node is NULL, create a new node
// with the given value and return it as the new root.
if(root==NULL){
return new TreeNode(val);
}

// cur pointer to traverse the tree
TreeNode* cur = root;

// While loop to traverse the tree to find
// the appropriate position for insertion.
while(true){
// If the current node's value is less
// than or equal to the value to be inserted,
// move to the right subtree.
if(cur->val <= val){
// If the right child of the current node
// is not NULL, update 'cur' to the right child.
if(cur->right !=NULL){
cur = cur->right;
}
// If the right child is NULL, create a new node
// with the given value as the right child
// and exit the while loop.
else{
cur->right = new TreeNode(val);
break;
}
}
// If the current node's value is greater than
// the value to be inserted,
// move to the left subtree.
else{
// If the left child of the current node
// is not NULL, update 'cur' to the left child.
if(cur->left !=NULL){
cur = cur->left;
}
// If the left child is NULL, create a new node
// with the given value as the left child
// and exit the while loop.
else{
cur->left = new TreeNode(val);
break;
}
}
}
// Return the root of the
// modified tree after insertion.
return root;
}
};

// Function to perform an in-order traversal
// of a binary tree and print its nodes
void printInOrder(TreeNode* root) {
// Check if the current node
// is null (base case for recursion)
if (root == NULL) {
// If null, return and
// terminate the function
return;
}

// Recursively call printInOrder
// for the left subtree
printInOrder(root->left);

// Print the value of the current node
cout << root->val << " ";

// Recursively call printInOrder
// for the right subtree
printInOrder(root->right);
}

int main() {
Solution solution;

// Creating a sample tree
TreeNode* root = new TreeNode(6);
root->left = new TreeNode(3);
root->right = new TreeNode(8);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(4);
root->right->left = new TreeNode(7);

// Printing the original tree
cout << "Original Tree (Inorder Traversal): ";
printInOrder(root);
cout << endl;

int keyToInsert = 5;
TreeNode* updatedTree = solution.insertIntoBST(root, keyToInsert);

cout << "Tree After Insertion (Inorder Traversal): ";
printInOrder(updatedTree);
cout << endl;

return 0;
}

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

## Java Code

class TreeNode {
// Value of the node
int val;
// Pointer to the left child node
TreeNode left;
// Pointer to the right child node
TreeNode right;

// Constructor to initialize the node with a value
// and set left and right pointers to null
TreeNode(int x) {
val = x;
left = null;
right = null;
}
}

class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
// If the root node is null, create a new node
// with the given value and return it as the new root
if (root == null) {
return new TreeNode(val);
}

// cur pointer to traverse the tree
TreeNode cur = root;

// While loop to traverse the tree to find
// the appropriate position for insertion
while (true) {
// If the current node's value is less
// than or equal to the value to be inserted,
// move to the right subtree
if (cur.val <= val) {
// If the right child of the current node
// is not null, update 'cur' to the right child
if (cur.right != null) {
cur = cur.right;
}
// If the right child is null, create a new node
// with the given value as the right child
// and exit the while loop
else {
cur.right = new TreeNode(val);
break;
}
}
// If the current node's value is greater than
// the value to be inserted,
// move to the left subtree
else {
// If the left child of the current node
// is not null, update 'cur' to the left child
if (cur.left != null) {
cur = cur.left;
}
// If the left child is null, create a new node
// with the given value as the left child
// and exit the while loop
else {
cur.left = new TreeNode(val);
break;
}
}
}
// Return the root of the modified tree after insertion
return root;
}
}

public class Main {
// Function to perform an in-order traversal
// of a binary tree and print its nodes
public static void printInOrder(TreeNode root) {
// Check if the current node is null
// (base case for recursion)
if (root == null) {
// If null, return and terminate the function
return;
}

// Recursively call printInOrder for the left subtree
printInOrder(root.left);

// Print the value of the current node
System.out.print(root.val + " ");

// Recursively call printInOrder for the right subtree
printInOrder(root.right);
}

public static void main(String[] args) {
Solution solution = new Solution();

// Creating a sample tree
TreeNode root = new TreeNode(6);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);

// Printing the original tree
System.out.print("Original Tree (Inorder Traversal): ");
printInOrder(root);
System.out.println();

int keyToInsert = 5;
TreeNode updatedTree = solution.insertIntoBST(root, keyToInsert);

System.out.print("Tree After Insertion (Inorder Traversal): ");
printInOrder(updatedTree);
System.out.println();
}
}

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

## Python Code

# Definition of TreeNode class for a binary tree node
class TreeNode:
# Constructor to initialize the node with a value
# and set left and right pointers to None
def __init__(self, x):
self.val = x
self.left = None
self.right = None

# Solution class with insertIntoBST method
class Solution:
def insertIntoBST(self, root, val):
# If the root node is None, create a new node
# with the given value and return it as the new root.
if not root:
return TreeNode(val)

# cur pointer to traverse the tree
cur = root

# While loop to traverse the tree to find
# the appropriate position for insertion.
while True:
# If the current node's value is less
# than or equal to the value to be inserted,
# move to the right subtree.
if cur.val <= val:
# If the right child of the current node
# is not None, update 'cur' to the right child.
if cur.right:
cur = cur.right
# If the right child is None, create a new node
# with the given value as the right child
# and exit the while loop.
else:
cur.right = TreeNode(val)
break
# If the current node's value is greater than
# the value to be inserted,
# move to the left subtree.
else:
# If the left child of the current node
# is not None, update 'cur' to the left child.
if cur.left:
cur = cur.left
# If the left child is None, create a new node
# with the given value as the left child
# and exit the while loop.
else:
cur.left = TreeNode(val)
break

# Return the root of the
# modified tree after insertion.
return root

# Function to perform an in-order traversal
# of a binary tree and print its nodes
def printInOrder(root):
# Check if the current node
# is None (base case for recursion)
if not root:
# If None, return and
# terminate the function
return

# Recursively call printInOrder
# for the left subtree
printInOrder(root.left)

# Print the value of the current node
print(root.val, end=" ")

# Recursively call printInOrder
# for the right subtree
printInOrder(root.right)

def main():
solution = Solution()

# Creating a sample tree
root = TreeNode(6)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.left = TreeNode(7)

# Printing the original tree
print("Original Tree (Inorder Traversal): ", end="")
printInOrder(root)
print()

keyToInsert = 5
updatedTree = solution.insertIntoBST(root, keyToInsert)

print("Tree After Insertion (Inorder Traversal): ", end="")
printInOrder(updatedTree)
print()

if __name__ == "__main__":
main()

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

## JavaScript Code

// Definition of TreeNode structure
// for a binary tree node
class TreeNode {
// Constructor to initialize
// the node with a value
constructor(x) {
this.val = x;
// Pointer to the left child node
this.left = null;
// Pointer to the right child node
this.right = null;
}
}

class Solution {
insertIntoBST(root, val) {
// If the root node is null, create a new node
// with the given value and return it as the new root.
if (root === null) {
return new TreeNode(val);
}

// cur pointer to traverse the tree
let cur = root;

// While loop to traverse the tree to find
// the appropriate position for insertion.
while (true) {
// If the current node's value is less than
// or equal to the value to be inserted,
// move to the right subtree.
if (cur.val <= val) {
// If the right child of the current node
// is not null, update 'cur' to the right child.
if (cur.right !== null) {
cur = cur.right;
}
// If the right child is null, create a
// new node with the given value as the
// right child and exit the loop.
else {
cur.right = new TreeNode(val);
break;
}
}
// If the current node's value is greater than the
// value to be inserted, move to the left subtree.
else {
// If the left child of the current node is not
// null, update 'cur' to the left child.
if (cur.left !== null) {
cur = cur.left;
}
// If the left child is null, create a
// new node with the given value as the
// left child and exit the loop.
else {
cur.left = new TreeNode(val);
break;
}
}
}
// Return the root of the
// modified tree after insertion.
return root;
}
}

// Function to perform an in-order traversal
// of a binary tree and print its nodes
function printInOrder(root) {
// Check if the current node is null
// (base case for recursion)
if (root === null) {
// If null, return and
// terminate the function
return;
}

// Recursively call printInOrder
// for the left subtree
printInOrder(root.left);

// Print the value of the current node
console.log(root.val + " ");

// Recursively call printInOrder
// for the right subtree
printInOrder(root.right);
}

// Creating a sample tree
let root = new TreeNode(6);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);

// Printing the original tree
console.log("Original Tree (Inorder Traversal): ");
printInOrder(root);
console.log("\n");

let keyToInsert = 5;
let solution = new Solution();
let updatedTree = solution.insertIntoBST(root, keyToInsert);

console.log("Tree After Insertion (Inorder Traversal): ");
printInOrder(updatedTree);
console.log("\n");

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.