L43. Insert a given Node in Binary Search Tree | BST | C++ | Java

Inserting a new node into a Binary Search Tree (BST) while strictly maintaining the foundational BST ordering property. This lecture breaks down the optimal search-and-insert approach, standard corner cases, iterative implementations in both C++ and Java, and complexity analysis.

1. Why Do We Need This? (Problem Statement & Status Quo)

• The Challenge: You are given the root of an existing Binary Search Tree and a target integer value (e.g., 5) that does not currently exist in the tree.
• The Goal: Insert the new node anywhere in the BST such that the BST Property remains intact:
  • For any given node, all values in its left subtree must be strictly smaller than the node's value.
  • All values in its right subtree must be strictly greater than the node's value.
  • Both left and right subtrees must themselves remain valid BSTs.
• Flexibility: There is no single "correct" structural location. You can insert the node at various valid leaf positions as long as the resulting tree satisfies all BST invariants. The objective is to return the root of the modified binary search tree after successful insertion.

2. Core Mental Model: The "Find and Plant" Strategy

Real-Life Analogy: Think of a corporate organizational chart sorted by employee ID numbers. If you want to hire a new employee with ID 50, you start at the CEO's office. If 50 is greater than the CEO's ID, you walk down the right hallway. If that manager's ID is smaller, you walk down their left hallway. You keep walking down the correct hallway based on comparisons until you hit a closed office door (null). That dead end is precisely where the new employee's desk belongs!

• Key Insight: You do not need to rebalance the entire tree or shift existing nodes around.
• The new node will always be attached at a leaf position where a null link currently resides.
• The problem guarantees that the value to be inserted does not already exist in the tree.

3. Visualizing Multiple Valid Insertion Outcomes

Given a base BST, a value like 5 can be inserted in multiple valid positions depending on the traversal path chosen:

Base BST:
       4
     /   \
    2     7
   / \   
  1   3  

Possible Insertion 1 (Attaching as a leaf):
       4
     /   \
    2     7
   / \   /
  1   3 5  (5 placed on the left of 7)

Possible Insertion 2 (Inserting in-between nodes):
       4
     /   \
    2     7
   / \   
  1   3
       \
        5  (5 placed as right child of 3)

4. Step-by-Step Algorithmic Evolution

1. Handle the Empty Tree Edge Case: If the root is null, the new value becomes the root node immediately. Return a newly created node with that value.
2. Initialize a Traversal Pointer: Create a pointer (curr) starting at the root. We keep a permanent reference to the root so we can return it at the very end.
3. Iterative Search Loop:
   • Compare the target value with the current node's value (curr->val).
   • If val > curr->val, the target belongs in the right subtree.
     • Check if curr->right is null. If it is, instantiate the new node right there and break out of the loop.
     • Otherwise, move curr to curr->right.
   • If val < curr->val, the target belongs in the left subtree.
     • Check if curr->left is null. If it is, instantiate the new node right there and break out of the loop.
     • Otherwise, move curr to curr->left.
4. Return Root: Return the original root reference.

5. Complete Code Implementations (C++ & Java)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // Base Case: If the tree is empty, return a new node as root
        if (root == nullptr) {
            return new TreeNode(val);
        }
        
        TreeNode* curr = root;
        
        while (true) {
            if (curr->val <= val) {
                // Move or insert to the right subtree
                if (curr->right != nullptr) {
                    curr = curr->right;
                } else {
                    curr->right = new TreeNode(val);
                    break;
                }
            } else {
                // Move or insert to the left subtree
                if (curr->left != nullptr) {
                    curr = curr->left;
                } else {
                    curr->left = new TreeNode(val);
                    break;
                }
            }
        }
        
        return root;
    }
};

Java Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // Base Case: If the tree is empty, return a new node as root
        if (root == null) {
            return new TreeNode(val);
        }
        
        TreeNode curr = root;
        
        while (true) {
            if (curr.val <= val) {
                // Move or insert to the right subtree
                if (curr.right != null) {
                    curr = curr.right;
                } else {
                    curr.right = new TreeNode(val);
                    break;
                }
            } else {
                // Move or insert to the left subtree
                if (curr.left != null) {
                    curr = curr.left;
                } else {
                    curr.left = new TreeNode(val);
                    break;
                }
            }
        }
        
        return root;
    }
}

6. Detailed Walkthrough of Dry Run

Let's trace the algorithm with:

• BST: Root is 4, with left child 2 and right child 7.
• Target Value: 5

7. Complexity Analysis

8. Summary and Key Takeaways

• BST Invariant Preservation: Inserting a node requires keeping the left-child-smaller and right-child-greater rule strictly enforced at every level.
• Leaf Insertion Point: New nodes are always attached at an existing null pointer position acting as a leaf.
• Uniqueness Guarantee: The problem assumes the inserted value is guaranteed not to exist in the tree beforehand.
• Iterative Approach: Using a while loop with a tracking pointer (curr) avoids recursive call-stack overhead, achieving optimal $O(1)$ auxiliary space.
• Pointer Preservation: Always keep a reference to the original root node so it can be returned safely after the insertion loop terminates.