Problem Description

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Your task is to insert the new value into the BST and return the root node of the modified tree.

The problem guarantees that the value you're inserting does not already exist in the BST.

A binary search tree follows these properties:

• For any node, all values in its left subtree are less than the node's value
• For any node, all values in its right subtree are greater than the node's value

There may be multiple valid positions where you can insert the new value while maintaining the BST properties. You can return any valid result.

For example, if you have a BST with root value 4, left child 2, and right child 7, and you need to insert value 5, you could insert it as the left child of 7. The tree would still maintain its BST properties since 5 is greater than 4 but less than 7.

The solution uses a recursive approach:

• If we reach a null position (empty spot), we create a new node with the given value
• If the current node's value is greater than the value to insert, we go to the left subtree
• If the current node's value is less than the value to insert, we go to the right subtree
• We continue this process until we find an appropriate empty position for the new node

Intuition

The key insight comes from understanding how we search for values in a BST. When looking for where to place a new value, we follow the same path we would take if we were searching for that value.

Think about it this way: if you're trying to insert value 5 into a BST, you would compare it with each node you encounter. If 5 is less than the current node, you go left; if it's greater, you go right. Eventually, you'll reach a point where there's no more nodes to compare with - that's exactly where the new value belongs.

This naturally leads to a recursive approach. At each node, we make a decision:

• If we've reached an empty spot (None), we've found where to insert our new node
• Otherwise, we compare the value with the current node and decide which direction to go

The beauty of this approach is that we don't need to restructure the existing tree. We simply traverse down to find an empty leaf position and attach the new node there. This guarantees the BST property is maintained because we're following the same comparison logic that defines a BST.

Why does recursion work so well here? Because the problem has a recursive structure - a BST is essentially a root node with two smaller BSTs as children. When we insert into the left or right subtree, we're solving the same problem on a smaller scale. The base case is when we hit a None node, where we simply create and return the new node.

The recursive calls also handle the linking automatically. When we call root.left = self.insertIntoBST(root.left, val), we're either keeping the existing left child (if insertion happens deeper in the tree) or replacing None with the new node (if we've reached the insertion point).

Learn more about Tree, Binary Search Tree and Binary Tree patterns.

Solution Approach

The solution uses a recursive approach to traverse the BST and find the correct position for the new value.

Let's walk through the implementation step by step:

Base Case:

if root is None:
    return TreeNode(val)

When we encounter a None node (empty position), we've found where to insert our new value. We create a new TreeNode with the given value and return it. This becomes a leaf node in the BST.

Recursive Cases:

if root.val > val:
    root.left = self.insertIntoBST(root.left, val)
else:
    root.right = self.insertIntoBST(root.right, val)

Here we compare the value to insert with the current node's value:

• If root.val > val, the new value should go in the left subtree (BST property: smaller values go left)
• Otherwise (root.val < val), the new value should go in the right subtree (BST property: larger values go right)

The key insight is that we recursively call insertIntoBST on the appropriate subtree and assign the result back to either root.left or root.right. This serves two purposes:

1. If the insertion happens deeper in the tree, it maintains the existing connection
2. If the child is None, it connects the newly created node to the parent

Return Statement:

return root

After the insertion is complete, we return the root of the tree. This is crucial for maintaining connections as we backtrack through the recursion.

The algorithm follows this pattern:

1. Start at the root and compare values
2. Navigate left or right based on the comparison
3. Continue until finding a None position
4. Create the new node at that position
5. Backtrack through recursion, maintaining all parent-child connections

Time Complexity: O(h) where h is the height of the tree. In the worst case (skewed tree), this could be O(n). Space Complexity: O(h) for the recursion call stack.

Example Walkthrough

Let's walk through inserting value 5 into this BST:

Initial BST:
      4
     / \
    2   7
   /
  1

Step 1: Start at root (4)

• Compare: 5 > 4, so we need to go right
• Recursive call: insertIntoBST(node_7, 5)

Step 2: At node 7

• Compare: 5 < 7, so we need to go left
• Check: node_7.left is None (empty spot found!)
• Recursive call: insertIntoBST(None, 5)

Step 3: At None (base case)

• Create new TreeNode(5)
• Return this new node

Step 4: Backtrack to node 7

• Assign: node_7.left = TreeNode(5)
• Return node_7

Step 5: Backtrack to root (4)

• Assign: root.right = node_7 (maintains existing connection)
• Return root

Final BST:
      4
     / \
    2   7
   /   /
  1   5

The key insight is how the recursive returns maintain the tree structure:

• When we hit None, we create and return the new node
• Each recursive level assigns the returned value to either left or right child
• Existing nodes simply return themselves, preserving the original structure
• Only the None position gets replaced with the new node

This ensures the BST property is maintained: 1 < 2 < 4 < 5 < 7, and each node's left children are smaller while right children are larger.

Solution Implementation

Time and Space Complexity

The time complexity is O(h) where h is the height of the BST. In the worst case when the tree is skewed (essentially a linked list), h = n, making the time complexity O(n). In the best case of a balanced BST, h = log(n), making the time complexity O(log n). The algorithm traverses from root to a leaf position where the new node should be inserted, visiting at most h nodes.

The space complexity is O(h) due to the recursive call stack. Similar to time complexity, in the worst case of a skewed tree, the recursion depth reaches n, making the space complexity O(n). In the best case of a balanced tree, the recursion depth is log(n), making the space complexity O(log n). Each recursive call uses constant extra space, but the call stack accumulates up to h function calls before returning.

The reference answer stating O(n) for both complexities represents the worst-case scenario where the BST degenerates into a linear structure with height equal to the number of nodes n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Assign the Recursive Call Result

A common mistake is calling the recursive function without assigning its return value back to the parent's child pointer:

Incorrect Code:

if root.val > val:
    self.insertIntoBST(root.left, val)  # Missing assignment!
else:
    self.insertIntoBST(root.right, val)  # Missing assignment!
return root

Why This Fails: When root.left or root.right is None, the recursive call creates a new node, but without assignment, this new node never gets connected to the parent. The tree remains unchanged, and the value is never actually inserted.

Correct Approach:

if root.val > val:
    root.left = self.insertIntoBST(root.left, val)  # Properly assigns the result
else:
    root.right = self.insertIntoBST(root.right, val)  # Properly assigns the result
return root

2. Handling Edge Case of Empty Tree Incorrectly

Another pitfall is not handling the case when the initial root is None:

Incorrect Code:

def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if root.val > val:  # This will crash if root is None!
        if root.left is None:
            root.left = TreeNode(val)
        else:
            self.insertIntoBST(root.left, val)
    # ... rest of code

Why This Fails: If the tree is initially empty (root is None), accessing root.val will raise an AttributeError.

Correct Approach: Always check if the root is None first:

if root is None:
    return TreeNode(val)
# Then proceed with comparisons

3. Using Iterative Approach Without Proper Parent Tracking

When attempting an iterative solution, a common mistake is losing track of the parent node:

Incorrect Iterative Attempt:

def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if not root:
        return TreeNode(val)
  
    current = root
    while current:
        if val < current.val:
            current = current.left  # We lose the parent reference!
        else:
            current = current.right
  
    current = TreeNode(val)  # This doesn't attach to the tree!
    return root

Correct Iterative Approach:

def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if not root:
        return TreeNode(val)
  
    current = root
    while True:
        if val < current.val:
            if current.left is None:
                current.left = TreeNode(val)
                break
            current = current.left
        else:
            if current.right is None:
                current.right = TreeNode(val)
                break
            current = current.right
  
    return root

The recursive approach naturally handles parent-child connections through the call stack, making it less error-prone for this problem.