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.

Examples

Example 1

graph LR;
subgraph Original["Before Insert"]
	A(1)
	B(2)
	C(3)
	D(4)
	G(7)
	D --- B & G
	B --- A & C
end

subgraph Option1["After Insertion - Possibility 1"]
	A2(1)
	B2(2)
	C2(3)
	D2(4)
	G2(7)
	E2(5):::blueShade
	D2 --- B2 & G2
	B2 --- A2 & C2
	G2 --- E2
	G2 ~~~ N1:::hidden
end

subgraph Option2["After Insertion - Possibility 2"]
	A3(1)
	B3(2)
	C3(3)
	D3(4)
	G3(7)
	E3(5):::blueShade
	
	E3 --- B3 & G3
	B3 --- A3 & C3
	C3 ~~~ N2:::hidden
	C3 --- D3
end

Original --- Option1 & Option2
classDef hidden display:none
classDef blueShade fill:#1E90FF,stroke:#000,stroke-width:1px,color:#fff;
  
1
2
3

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Solution

Method 1 - Recursive

Binary Search Trees (BSTs) maintain the property that for any node:

  • All values in the left subtree are smaller than the node’s value.
  • All values in the right subtree are greater than the node’s value.

To insert a new value into the BST:

  1. Traverse the tree starting from the root.
  2. Compare the new value to the current node’s value:
    • If the value is smaller, move to the left subtree.
    • If the value is larger, move to the right subtree.
  3. Once a None (or null) position is found in the correct subtree (where the new value logically fits), create a new node with the value and assign it to this position.

The problem guarantees that the new value does not exist in the BST, so we don’t have to handle duplicates.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val); // Base case: if root is null, create and return a new node
        }

        if (val < root.val) {
            root.left = insertIntoBST(root.left, val); // Recursive case for left subtree
        } else { // val > root.val
            root.right = insertIntoBST(root.right, val); // Recursive case for right subtree
        }

        return root; // Return the unchanged root
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)  # Base case: if root is None, create and return a new node

        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)   # Recursive case for the left subtree
        else:
            root.right = self.insertIntoBST(root.right, val) # Recursive case for the right subtree

        return root  # Return the unchanged root

Method 1 - Recursive Solution

Complexity

  • ⏰ Time complexity: O(h) where h is the height of the BST. In the worst case (unbalanced tree), h is n (number of nodes). For a balanced BST, h is log(n).
  • 🧺 Space complexity: O(h) in the recursive approach because of the stack frames in recursion. The iterative approach uses constant space O(1).

Method 2 - Iterative Solution

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val); // If root is null, create the new node and return
        }

        TreeNode cur = root; // Start traversing from the root
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) {
                    cur.left = new TreeNode(val); // Found the insertion point
                    break;
                } else {
                    cur = cur.left; // Move to the left subtree
                }
            } else { // val > cur.val
                if (cur.right == null) {
                    cur.right = new TreeNode(val); // Found the insertion point
                    break;
                } else {
                    cur = cur.right; // Move to the right subtree
                }
            }
        }

        return root; // Return the unchanged root
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)  # If the root is None, create and return a new node
        
        cur = root  # Start traversal from the root
        while cur:
            if val < cur.val:
                if not cur.left:
                    cur.left = TreeNode(val)  # Insert into the left
                    break
                else:
                    cur = cur.left  # Move to the left subtree
            else:  # val > cur.val
                if not cur.right:
                    cur.right = TreeNode(val)  # Insert into the right
                    break
                else:
                    cur = cur.right  # Move to the right subtree
        
        return root  # Return the unchanged root

Complexity

  • ⏰ Time complexity: O(h)
  • 🧺 Space complexity: O(1)