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&nbsp;that there may exist&nbsp;multiple valid ways for the&nbsp;insertion, as long as the tree remains a BST after insertion. You can return any of them.

&nbsp;
Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:



Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]


Example 3:

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


&nbsp;
Constraints:


	The number of nodes in&nbsp;the tree will be in the range [0,&nbsp;104].
	-108 &lt;= Node.val &lt;= 108
	All the values Node.val are unique.
	-108 &lt;= val &lt;= 108
	It's guaranteed that val does not exist in the original BST.


class Solution:
    def insertIntoBST(self, root, val):
        if not root:
            return TreeNode(val)
      
        if val<root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
  
        return root
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
      
     if(root.val > val) root.left = insertIntoBST(root.left, val);
      
      else root.right = insertIntoBST(root.right, val);
      
      return root;
    }
}
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==NULL) return new TreeNode(val);
        TreeNode* node = root;
        while(true){
            if(val>=node->val){
                if(node->right) node = node->right;
                else{
                    node->right = new TreeNode(val);
                    break;
                }
            }
            else{
                if(node->left) node = node->left;
                else{
                    node->left = new TreeNode(val);
                    break;
                }
            }
        }
        return root;
    }
};
var insertIntoBST = function(root, 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;
};
Insert into a Binary Search Tree