# Insert into a Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/insert-into-a-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/insert-into-a-binary-search-tree
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
You are given the `root` node of a binary search tree (BST) and a `value` to insert into the tree. Return _the root node of the BST after the insertion_. It is **guaranteed** that the new value does not exist in the original BST.

**Notice** that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return **any of them**.

**Example 1:**

![](https://assets.glich.co/dsa/insert-into-a-binary-search-tree/image0.jpg) 

**Input:** root = [4,2,7,1,3], val = 5
**Output:** [4,2,7,1,3,5]
**Explanation:** Another accepted tree is:
![](https://assets.glich.co/dsa/insert-into-a-binary-search-tree/image1.jpg)

**Example 2:**

**Input:** root = [40,20,60,10,30,50,70], val = 25
**Output:** [40,20,60,10,30,50,70,null,null,25]

**Example 3:**

**Input:** root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
**Output:** [4,2,7,1,3,5]

**Constraints:**

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

# Approaches
## Recursive Insertion
This approach uses recursion to traverse the binary search tree. It leverages the inherent recursive structure of a tree. The function calls itself on either the left or right subtree based on the comparison between the new value and the current node's value, until it finds an empty spot (a null child) to place the new node.
**Time:** O(H), where H is the height of the tree. In each step, we move one level down the tree. In the average case for a balanced BST, H is O(log N). In the worst case of a completely unbalanced (skewed) tree, H is O(N), where N is the number of nodes. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. In the average case for a balanced BST, H is approximately log(N), making the complexity O(log N). In the worst case of a skewed tree, H is N, leading to O(N) complexity.
**Pros:** The code is often more concise and elegant, closely mirroring the mathematical definition of a BST.; It's a very natural way to solve tree problems and can be easier to reason about.
**Cons:** The space complexity is proportional to the height of the tree due to the recursion stack.; It can lead to a stack overflow error for very deep or skewed trees.
### Explanation
The core idea is to define a function that takes a node and a value. If the node is null, it means we've found the insertion point. We create a new `TreeNode` with the given value and return it. If the value to be inserted is less than the current node's value, we recursively call the function on the left child. The result of this recursive call (the potentially modified left subtree) is then assigned back to the current node's left child pointer. If the value is greater, we do the same for the right child. Finally, the function returns the current node, which ensures the tree structure is correctly linked back up the recursion chain. The initial call would be `insertIntoBST(root, val)`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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;
    }
}
```
### Algorithm
*   1. Define a recursive function `insertIntoBST(node, val)`.
*   2. **Base Case:** If `node` is `null`, create a new `TreeNode` with `val` and return it. This is the position where the new node should be inserted.
*   3. **Recursive Step:**
    *   a. If `val` is less than `node.val`, the new node belongs in the left subtree. Recursively call `insertIntoBST` on the left child: `node.left = insertIntoBST(node.left, val)`.
    *   b. If `val` is greater than `node.val`, the new node belongs in the right subtree. Recursively call `insertIntoBST` on the right child: `node.right = insertIntoBST(node.right, val)`.
*   4. Return the `node`. The returned node is then linked back to its parent in the previous recursive call.

## Iterative Insertion
This approach uses a loop to traverse the tree from the root down to find the correct insertion point. By using a pointer to keep track of the current node, it avoids recursion and the associated overhead of the call stack, making it more space-efficient.
**Time:** O(H), where H is the height of the tree. The number of iterations in the loop is determined by the depth of the insertion point. On average, for a balanced tree, this is O(log N). In the worst case of a skewed tree, it is O(N). · **Space:** O(1). This approach uses a constant amount of extra space for the `current` pointer, regardless of the tree's size or shape.
**Pros:** Optimal space complexity of O(1) as it only uses a few pointers.; Avoids the risk of stack overflow, making it robust for very deep or skewed trees.
**Cons:** The code can be slightly more verbose and less intuitive for those accustomed to recursive solutions for tree problems.
### Explanation
First, we handle the edge case of an empty tree. If the `root` is `null`, we create a new node and return it. If the tree is not empty, we use a pointer, let's call it `current`, initialized to the `root`. We then loop, traversing down the tree. Inside the loop, we compare the `val` with `current.val`. If `val` is smaller, we check the left child. If `current.left` is `null`, we've found the insertion point. We create the new node, attach it as `current.left`, and terminate the loop. Otherwise, we move `current` to its left child (`current = current.left`). A similar process is followed if `val` is larger, but for the right child. Since the problem guarantees the value is not already in the tree, this loop will always find a null link to attach the new node. Finally, we return the original `root`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        
        TreeNode current = root;
        while (true) {
            if (val < current.val) {
                if (current.left == null) {
                    current.left = new TreeNode(val);
                    break;
                }
                current = current.left;
            } else { // val > current.val
                if (current.right == null) {
                    current.right = new TreeNode(val);
                    break;
                }
                current = current.right;
            }
        }
        return root;
    }
}
```
### Algorithm
*   1. Handle the edge case: If the `root` is `null`, create a new `TreeNode` with `val` and return it.
*   2. Initialize a pointer `current` to `root`.
*   3. Start a `while` loop that continues until the node is inserted.
*   4. Inside the loop, compare `val` with `current.val`:
    *   a. If `val < current.val`:
        *   i. If `current.left` is `null`, this is the insertion point. Create a new `TreeNode(val)`, set `current.left` to this new node, and `break` the loop.
        *   ii. Otherwise, the search must continue in the left subtree. Update `current` to `current.left`.
    *   b. If `val > current.val`:
        *   i. If `current.right` is `null`, this is the insertion point. Create a new `TreeNode(val)`, set `current.right` to this new node, and `break` the loop.
        *   ii. Otherwise, the search must continue in the right subtree. Update `current` to `current.right`.
*   5. After the loop terminates, return the original `root`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode insertIntoBST ( TreeNode root , int val ) { if ( root == null ) { return new TreeNode ( val ); } if ( root . val < val ) { root . right = insertIntoBST ( root . right , val ); } else { root . left = insertIntoBST ( root . left , val ); } return root ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * insertIntoBST ( TreeNode * root , int val ) { if ( ! root ) return new TreeNode ( val ); if ( root -> val < val ) root -> right = insertIntoBST ( root -> right , val ); else root -> left = insertIntoBST ( root -> left , val ); return root ; } };
```

### Python

```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 : TreeNode , val : int ) -> TreeNode : def dfs ( root ): if root is None : return TreeNode ( val ) if root . val < val : root . right = dfs ( root . right ) else : root . left = dfs ( root . left ) return root return dfs ( root )
```