Insert into a Binary Search Tree - The Coding Shala

Last Updated: 19-Jan-2021
Home >> Data Structures >> Insert into a Binary Search Tree

 In this post, we will learn how to Insert a Node into a Binary Search Tree.

Insert into a Binary Search Tree

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,
Given the tree:
        4
       / \
      2   7
     / \
    1   3
And the value to insert: 5
You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

This tree is also valid:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

Java Program to Insert Node into Binary Search Tree

Approach 1

Iterative Solution.

Java Program: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            root = new TreeNode(val);
            return root;
        }
        TreeNode curr = root;
        while(curr != null){
            if(val < curr.val && curr.left == null){
                curr.left = new TreeNode(val);
                break;
            } else if(val> curr.val && curr.right == null){
                curr.right = new TreeNode(val);
                break;
            }else if(val < curr.val) curr = curr.left;
            else curr = curr.right;
        }
        return root;
    }
}

Approach 2

Using Recursion.

Java Program: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val);
        }
        
        if(val < root.val){
            root.left = insertIntoBST(root.left, val);
        }else{
            root.right = insertIntoBST(root.right, val);
        }
        
        return root;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Add two numbers in Scala - The Coding Shala