Solution Inserting a new node in a BST

Problem Statement

Write Recursive Approach to Insert New Node in a Binary Search Tree.

Given a binary search tree (BST) and a value to be inserted, write a recursive algorithm to insert a new node with the given value into the BST while maintaining its properties.

Examples

1. BST Before Insertion:

       4
      / \
     2   7
    / \
   1   3

   Input Node: 5 Output BST:

       4
      / \
     2   7
    / \   \
   1   3   5

   Explanation: The input node with value 5 is inserted as the right child of node 7.

2. BST Before Insertion:

       6
      / \
     3   8
    / \   \
   1   5   9

   Input Node: 4 Output BST:

       6
      / \
     3   8
    / \   \
   1   5   9
        /
       4

   Explanation: The input node with value 4 is inserted as the left child of node 5.

3. BST Before Insertion: Empty BST (null) Input Node: 2 Output BST:

      2

   Explanation: The input node with value 2 becomes the root of the BST.

Constraints:

• The number of nodes in the tree will be in the range [0, 10⁴].
• -10⁸ <= Node.val <= 10⁸
• All the values Node.val are unique.
• -10⁸ <= val <= 10⁸
• It's guaranteed that val does not exist in the original BST.

Solution

The recursive approach to insert a new node in a BST can be summarized as follows:

• If the BST is empty (null), create a new node with the given value and return it.
• If the value to be inserted is less than the value of the current node, recursively call the insert function on the left subtree.
• If the value to be inserted is greater than the value of the current node, recursively call the insert function on the right subtree.
• Finally, return the modified BST.

This approach works because it follows the property of a BST, where all nodes in the left subtree are smaller than the current node, and all nodes in the right subtree are greater than the current node.

Code

Here is the code for this algorithm:

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

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

public class Solution {

  public TreeNode insert(TreeNode root, int value) {
    if (root == null) {
      // Base case: create a new node with the given value
      return new TreeNode(value);
    }

    if (value < root.val) {
      // Recursive case: insert into the left subtree
      root.left = insert(root.left, value);
    } else if (value > root.val) {
      // Recursive case: insert into the right subtree
      root.right = insert(root.right, value);
    }

    // Return the modified BST
    return root;
  }

  public static void main(String[] args) {
    // Example inputs
    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[] values = { 5, 4, 2 };

    Solution bstInsertion = new Solution();

    // Insert nodes into the BST
    for (int value : values) {
      root = bstInsertion.insert(root, value);
    }

    // Print the updated BST
    System.out.println("BST After Insertion:");
    printBST(root);
  }

  private static void printBST(TreeNode node) {
    if (node == null) {
      return;
    }

    printBST(node.left);
    System.out.print(node.val + " ");
    printBST(node.right);
  }
}

Time and Space Complexity

The time and space complexity of the algorithm is , where h is the height of the BST. In the worst case, where the BST is skewed (i.e., a linked list), the height h is equal to the number of nodes in the BST, resulting in time and space complexity. However, in a balanced BST, the height h is logarithmic to the number of nodes, resulting in efficient operations with time and space complexity.

I'm working on the problem **Solution Inserting a new node in a BST** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Solution Inserting a new node in a BST** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Solution Inserting a new node in a BST**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Solution Inserting a new node in a BST**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.