Problem Statement

Given a BST and a key K. If K is not present in the BST, Insert a new Node with a value equal to K into the BST. Note: If K is already present in the BST, don't modify the BST.

Example 1:

Input:
     2
   /   \\
  1     3
K = 4
Output:1 2 3 4
Explanation:After inserting the node 4
Inorder traversal will be 1 2 3 4.

Example 2:

Input:
        2
      /   \\
     1     3
             \\
              6
K = 4
Output:1 2 3 4 6
Explanation:After inserting the node 4
Inorder traversal of the above tree
will be 1 2 3 4 6.

Problem Link

Insert a node in a BST | Practice | GeeksforGeeks

Code

//Function to insert a node in a BST.
bool isPresent(Node *root,int key)
{
    if(!root)
    return false;
    
    if(root->data==key)
    return true;
    
    return isPresent(root->left,key)||isPresent(root->right,key);
}
Node* solve(Node*root,int key)
{
    if(!root)
    return new Node(key);
    
    
    if(key<root->data)
    root->left = insert(root->left,key);
    
    else
    root->right = insert(root->right,key);
    return root;
}
Node* insert(Node* root, int key)
{
   
    
   
    if(isPresent(root,key))
    return root;
    
    return solve(root,key);
}

Time Complexity: O(n)