# LeetCode 701: Insert into a Binary Search Tree

## Problem Restatement

We are given the root of a binary search tree and a value `val`.

We need to insert `val` into the tree while keeping the binary search tree property valid.

A binary search tree has this rule:

| Position | Rule |
|---|---|
| Left subtree | Values are smaller than the current node |
| Right subtree | Values are greater than the current node |

The problem guarantees that `val` does not already exist in the tree.

Return the root of the tree after insertion.

There may be more than one valid insertion result. Any valid BST is accepted.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root node of a BST |
| Input | `val`, the value to insert |
| Output | The root node of the modified BST |
| Guarantee | `val` does not already exist in the original BST |

The function shape is:

```python
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        ...
```

## Examples

Example 1:

```python
root = [4, 2, 7, 1, 3]
val = 5
```

The value `5` should be inserted into the BST.

Start at `4`.

Since `5 > 4`, go right to `7`.

Since `5 < 7`, go left.

The left child of `7` is empty, so insert `5` there.

One valid output is:

```python
[4, 2, 7, 1, 3, 5]
```

Example 2:

```python
root = [40, 20, 60, 10, 30, 50, 70]
val = 25
```

Start at `40`.

`25 < 40`, so go left to `20`.

`25 > 20`, so go right to `30`.

`25 < 30`, so go left.

The left child of `30` is empty, so insert `25` there.

## First Thought: Rebuild the Tree

One possible idea is to collect all values from the tree, add `val`, sort the values, and build a new BST.

That works, but it does much more work than needed.

We do not need to change the whole tree. A BST already tells us where the new value belongs. We only need to walk down one path from the root to an empty child position.

## Problem With Rebuilding

Rebuilding visits every node.

If the tree has `n` nodes, this costs at least:

```python
O(n)
```

It also uses extra memory to store all values.

But insertion into a BST only depends on the tree height `h`.

If the tree is balanced, `h` is about `log n`.

So a direct insertion can be much cheaper than rebuilding the full tree.

## Key Insight

At every node, the BST property tells us exactly which direction to go.

If `val` is smaller than the current node value, it belongs somewhere in the left subtree.

If `val` is greater than the current node value, it belongs somewhere in the right subtree.

We continue until we find an empty child position.

That empty position is a valid place to insert the new node.

## Algorithm

Use recursive traversal.

At each node:

1. If the current node is `None`, create and return a new node with `val`.
2. If `val < root.val`, insert `val` into the left subtree.
3. If `val > root.val`, insert `val` into the right subtree.
4. Return `root`.

The recursive return is important.

When insertion happens under a child pointer, the call returns the modified subtree root. We assign it back to `root.left` or `root.right`.

## Correctness

We prove that the algorithm returns a valid BST containing all original nodes plus `val`.

If `root` is `None`, the algorithm creates a single node containing `val`. A single-node tree is a valid BST.

Now assume `root` is not `None`.

If `val < root.val`, the value must be inserted into the left subtree to preserve the BST ordering. The algorithm recursively inserts it there. By the recursive assumption, the left subtree remains a valid BST and contains `val`. Since `val` is smaller than `root.val`, and every node in the left subtree is still on the left side of `root`, the full tree remains valid.

If `val > root.val`, the same reasoning applies to the right subtree. The inserted value belongs on the right side of `root`, and the recursive call preserves the right subtree as a valid BST.

The algorithm never moves or changes existing node values. It only attaches one new node at an empty position reached by valid BST comparisons. Therefore the returned tree contains all original nodes, contains `val`, and satisfies the BST property.

## Complexity

Let `h` be the height of the tree.

| Metric | Value | Why |
|---|---|---|
| Time | `O(h)` | We follow one path from root to insertion position |
| Space | `O(h)` | Recursive call stack follows the same path |

If the tree is balanced, `h = O(log n)`.

If the tree is skewed, `h = O(n)`.

## Implementation

```python
# 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: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val)

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

        return root
```

## Code Explanation

The base case handles an empty position:

```python
if root is None:
    return TreeNode(val)
```

This is where the new value is inserted.

If the value is smaller than the current node, it must go into the left subtree:

```python
if val < root.val:
    root.left = self.insertIntoBST(root.left, val)
```

If the value is larger, it must go into the right subtree:

```python
else:
    root.right = self.insertIntoBST(root.right, val)
```

The problem guarantees that `val` does not already exist, so the `else` branch means `val > root.val`.

Finally, return the current root:

```python
return root
```

This keeps the original root of the tree unchanged unless the original tree was empty.

## Iterative Version

The recursive version is short and natural, but the iterative version avoids recursion stack space.

```python
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        new_node = TreeNode(val)

        if root is None:
            return new_node

        cur = root

        while True:
            if val < cur.val:
                if cur.left is None:
                    cur.left = new_node
                    break
                cur = cur.left
            else:
                if cur.right is None:
                    cur.right = new_node
                    break
                cur = cur.right

        return root
```

This version uses the same comparison logic.

The only difference is that it directly attaches the new node once it finds an empty child pointer.

## Iterative Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(h)` | We walk down one root-to-leaf path |
| Space | `O(1)` | We only use a few pointers |

## Testing

For local testing, we can insert values and verify the inorder traversal stays sorted.

A BST inorder traversal should produce values in increasing order.

```python
def inorder(root):
    if root is None:
        return []

    return inorder(root.left) + [root.val] + inorder(root.right)

def test_insert_into_bst():
    s = Solution()

    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)

    root = s.insertIntoBST(root, 5)

    assert inorder(root) == [1, 2, 3, 4, 5, 7]

    root = None
    root = s.insertIntoBST(root, 10)

    assert inorder(root) == [10]

    root = TreeNode(8)
    root.left = TreeNode(4)
    root.right = TreeNode(12)

    root = s.insertIntoBST(root, 2)

    assert inorder(root) == [2, 4, 8, 12]

    print("all tests passed")
```

Test coverage:

| Test | Why |
|---|---|
| Insert into middle position | Confirms normal BST insertion |
| Insert into empty tree | Confirms base case |
| Insert as new left leaf | Confirms smaller values go left |
| Inorder traversal check | Confirms the final tree remains a BST |