Insert into a Binary Search Tree

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

Notice 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.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class InsertIntoBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        int val = 5;

        TreeNode tree = insertIntoBST(root, val);
        printTree(tree);
    }

    static TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        // call for left subtree
        if (root.val > val)
            root.left = insertIntoBST(root.left, val);

        // call for right subtree
        else
            root.right = insertIntoBST(root.right, val);
        return root;

    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

TreeNode* insertIntoBST(TreeNode* root, int val) 
{
        if(root==NULL)
        {
           return new TreeNode(val);
        }

        //call for left subtree
        if(root->data>val)
               root->left=insertIntoBST(root->left,val);

        //call for right subtree
        else
             root->right= insertIntoBST(root->right,val);
        return root;
        
}
//function to print the tree
void printTree(TreeNode *root)
{
    queue<TreeNode*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         root=q.front();
         q.pop();
         if(root==NULL)
         {
             continue;
         }
         else
            vec.push_back(to_string(root->data));
        if(root!=NULL)
          {
              q.push(root->left);
              q.push(root->right);
          }
     }
      for(int i=0;i<vec.size()-1;i++)
        cout<<vec[i]<<",";
    cout<<vec[vec.size()-1];
}
int main()
{
    TreeNode *root=new TreeNode(4);
    root->left=new TreeNode(2);
    root->right=new TreeNode(7);
    root->left->left=new TreeNode(1);
    root->left->right=new TreeNode(3);
    int val=5;

    TreeNode *tree=insertIntoBST(root,val);
    
    printTree(tree);
    return 0;

}