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

• Introduction to Binary Search Tree
• Binary Tree Preorder Traversal
• Invert Binary Tree
• Count Unique Binary Search Trees
• Height of a Binary Tree

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