Problem Description

You are given the root node of a binary search tree (BST) and an integer value val. Your task is to insert val into the BST such that the tree remains a valid BST. You must return the root node of the modified BST.

• It is guaranteed that there is exactly one valid way to insert val into the tree.
• You must not modify the values of existing nodes in the BST.
• You cannot reuse or duplicate any elements in the tree.
• The input root may be null, representing an empty tree.

A BST is defined as a binary tree where for every node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater.

Thought Process

To solve this problem, we first recall the properties of a binary search tree. Inserting a value means finding the correct position where the BST property is maintained. The naive way would be to traverse the entire tree and look for a place to insert, but since BSTs are sorted, we can use this property to optimize our search.

We compare val with the current node’s value. If val is less, we move to the left child; if greater, we move to the right child. We repeat this process recursively or iteratively until we find a null spot, where we can insert the new node. This approach ensures we maintain the BST property and do not unnecessarily traverse the entire tree.

The key insight is that BSTs allow us to ignore half of the tree at each step, similar to how binary search works in arrays.

Solution Approach

Here is a step-by-step approach to insert a value into a BST:

1. Check if the tree is empty: If the root is null, create a new node with val and return it as the root.
2. Traverse the tree: Start from the root and compare val with the current node’s value.
   • If val < node.val, move to the left child.
   • If val > node.val, move to the right child.
3. Find the insertion point: Continue traversing until you find a null left or right child, which means this is the correct spot to insert the new value.
4. Insert the new node: Create a new node with val and attach it as the left or right child where appropriate.
5. Return the root: Since we are modifying the tree in-place, we return the original root node.

This algorithm can be implemented both recursively and iteratively. Recursion is more natural for tree problems, but iteration avoids stack overflow for very deep trees.

Example Walkthrough

Example: Given the BST:

      4
     / \
    2   7
   / \
  1   3
  

Insert val = 5.

1. Start at root (4). Since 5 > 4, move to the right child (7).
2. At node (7). Since 5 < 7, move to the left child, which is null.
3. Insert a new node with value 5 as the left child of 7.

The updated tree becomes:

      4
     / \
    2   7
   / \ /
  1  3 5
  

At each step, the BST property is maintained because we always insert in a position determined by comparisons.

Time and Space Complexity

Brute-force approach: If we ignored the BST property and traversed the entire tree, the time complexity would be O(N), where N is the number of nodes.

Optimized approach (BST property): By following the BST property, we only traverse one path from root to leaf. In a balanced BST, this path has length O(log N), so the time complexity is O(log N). In the worst case (completely unbalanced tree), the complexity is O(N).

Space complexity:

• Recursive solution: O(H) due to the call stack, where H is the height of the tree (O(log N) for balanced, O(N) for skewed).
• Iterative solution: O(1) extra space, since we only use pointers.

Summary

Inserting into a BST leverages the tree’s ordering property to efficiently find the correct position for a new value. By comparing the value at each node and moving left or right, we avoid unnecessary work and maintain the BST structure. This approach is efficient, elegant, and highlights the power of recursive and iterative tree algorithms.

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        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
      

// Definition for a binary tree node.
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) {
        if (!root) return new TreeNode(val);
        if (val < root->val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int 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;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
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;
};