Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Insert into a Binary Search Tree

MEDIUMProblemSolveExternal Links

Description

You are given the root node of a binary search tree (BST) and a val to insert into the tree.

A binary search tree is a tree where for every node:

  • All values in its left subtree are strictly less than the node's value.
  • All values in its right subtree are strictly greater than the node's value.

Your task is to insert val into the BST such that the BST property is maintained after insertion, and return the root node of the modified tree.

It is guaranteed that the new value does not already exist in the original BST. Note that there may be multiple valid ways to perform the insertion (the new node can be placed at different valid leaf positions), and you may return any valid result.

Examples

Example 1

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

The tree looks like:

      4
     / \
    2   7
   / \
  1   3

Output: [4, 2, 7, 1, 3, 5]

The resulting tree:

      4
     / \
    2   7
   / \ /
  1  3 5

Explanation: We need to insert value 5. Starting at root 4: since 5 > 4, go right to node 7. Since 5 < 7, go left — but node 7 has no left child. So we attach 5 as the left child of 7. The BST property is preserved: 5 is in the right subtree of 4 (5 > 4 ✓) and in the left subtree of 7 (5 < 7 ✓).

Example 2

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

The tree looks like:

         40
        /  \
      20    60
     / \   / \
   10  30 50  70

Output: [40, 20, 60, 10, 30, 50, 70, null, null, 25]

The resulting tree:

         40
        /  \
      20    60
     / \   / \
   10  30 50  70
      /
    25

Explanation: Starting at root 40: 25 < 40 → go left to 20. Then 25 > 20 → go right to 30. Then 25 < 30 → go left — node 30 has no left child. Attach 25 as the left child of 30. The BST invariant holds at every level.

Example 3

Input: root = [], val = 5

Output: [5]

Explanation: The tree is empty. The inserted value becomes the root of a new single-node tree.

Constraints

  • The number of nodes in the tree will be in the range [0, 10^4].
  • -10^8 ≤ Node.val ≤ 10^8
  • All the values Node.val are unique.
  • -10^8 ≤ val ≤ 10^8
  • It is guaranteed that val does not exist in the original BST.

Editorial

Brute Force

Intuition

The most straightforward way to insert into a BST is using recursion, which mirrors how BSTs are defined.

A BST has a recursive structure: each subtree is itself a BST. So insertion naturally follows a recursive pattern:

  • If the tree is empty (null node), create a new node with the given value and return it — this is the base case.
  • If the value to insert is less than the current node's value, it belongs somewhere in the left subtree. Recursively insert into the left subtree and update the left child pointer.
  • If the value is greater, it belongs in the right subtree. Recursively insert there instead.

Think of it like finding the right mailbox in a sorting post office. At each desk, they look at the address: "smaller? go to the left wing. Larger? go to the right wing." You keep walking until you find an empty slot, and that is where you place the letter.

The key insight is that a new value in a BST is always inserted as a leaf node — it never displaces existing nodes. We simply navigate down the tree following BST rules until we find the right empty spot.

Step-by-Step Explanation

Let's trace through Example 1: root = [4, 2, 7, 1, 3], val = 5

Tree:

      4
     / \
    2   7
   / \
  1   3

Step 1: Call insert(node 4, val=5). Node is not null. Compare: 5 > 4 → the value belongs in the right subtree.

Step 2: Recurse: insert(node 7, val=5). Node is not null. Compare: 5 < 7 → the value belongs in the left subtree.

Step 3: Recurse: insert(null, val=5). Node is null → base case reached! Create a new node with value 5 and return it.

Step 4: Back at node 7: set node 7's left child = the newly created node 5. Node 7 now has left child 5.

Step 5: Back at node 4: set node 4's right child = node 7 (unchanged, since node 7 was already the right child). Return node 4.

Step 6: The tree is now:

      4
     / \
    2   7
   / \ /
  1  3 5

BST property verified: 1 < 2 < 3 < 4 < 5 < 7 ✓

Recursive BST Insertion: Inserting 5 into [4, 2, 7, 1, 3] — Watch how recursion navigates down the tree by comparing val with each node, then creates a new leaf at the correct position.

Algorithm

  1. If the current node is null, create and return a new node with the given value (base case).
  2. If val < current node's value:
    • Recursively insert into the left subtree.
    • Set the current node's left child to the result of the recursive call.
  3. If val > current node's value:
    • Recursively insert into the right subtree.
    • Set the current node's right child to the result of the recursive call.
  4. Return the current node (its subtree now includes the new node).

Code

/**
 * 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 == nullptr) {
            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.
# 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
/**
 * 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;
    }
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the tree

We traverse a single path from the root down to a leaf position. At each level, we make one comparison and move either left or right. The number of levels we traverse is at most h. For a balanced BST, h = log n, giving O(log n). For a skewed BST (all nodes in a single chain), h = n, giving O(n) in the worst case.

Space Complexity: O(h), due to the recursion call stack

Each recursive call adds one frame to the call stack, and we recurse at most h times (the depth of the insertion path). For a balanced tree this is O(log n); for a skewed tree it is O(n). This is the key limitation of the recursive approach.

Why This Approach Is Not Efficient

The recursive approach is clean and elegant, but it uses O(h) space on the call stack. For a balanced tree with 10,000 nodes, the recursion depth is about 13 levels — no problem. But for a skewed tree with 10,000 nodes (e.g., values inserted in sorted order), the recursion goes 10,000 levels deep, risking a stack overflow.

More importantly, the recursion is unnecessary here. Unlike tree problems that require backtracking or combining results from subtrees, BST insertion follows a single downward path — there is no need to "return" intermediate results through the call stack. We simply walk down the tree until we find an empty slot, then attach the new node.

This observation leads to the optimal iterative approach: use a simple loop with a pointer to traverse down to the correct position, then link the new node. This achieves the same O(h) time but with O(1) auxiliary space — no call stack overhead at all.

Optimal Approach - Iterative Insertion

Intuition

Since BST insertion always places the new value as a leaf, we do not need recursion. We can simply walk down the tree with a pointer, comparing the value at each node to decide whether to go left or right, until we reach a null position. At that point, we attach the new node.

The trick is to keep track of the parent node as we descend. When we reach a null child, we know the parent is the node that should adopt the new node. We then check: should the new node be the parent's left child or right child?

Think of it like navigating a maze with only left and right turns. At each intersection, a sign tells you which way to go (left if your number is smaller, right if larger). You keep walking until you hit a dead end — that dead end is where you build your new room. You remember the last intersection (parent) so you can connect the hallway.

Step-by-Step Explanation

Let's trace through Example 2: root = [40, 20, 60, 10, 30, 50, 70], val = 25

Tree:

         40
        /  \
      20    60
     / \   / \
   10  30 50  70

Step 1: Initialize: current = node 40, parent = null. Create new node with value 25.

Step 2: Compare: 25 < 40 → go left. Set parent = node 40, current = node 20.

Step 3: Compare: 25 > 20 → go right. Set parent = node 20, current = node 30.

Step 4: Compare: 25 < 30 → go left. Set parent = node 30, current = null (node 30 has no left child).

Step 5: current is null → we found the insertion point. Check: 25 < parent.val (30)? Yes → attach as parent's left child.

Step 6: Set node 30's left child = new node 25.

Final tree:

         40
        /  \
      20    60
     / \   / \
   10  30 50  70
      /
    25

BST property holds: 25 is less than 30, greater than 20, and less than 40 — all valid.

Iterative BST Insertion: Inserting 25 into [40, 20, 60, 10, 30, 50, 70] — Watch the current pointer navigate down the tree comparing at each node, with the parent pointer trailing one step behind, until we find the null slot to attach the new leaf.

Algorithm

  1. Create a new node with the given value.
  2. If the tree is empty (root is null), return the new node as the root.
  3. Initialize two pointers: current = root, parent = null.
  4. While current is not null:
    a. Set parent = current.
    b. If val < current.val, move current to current.left.
    c. Otherwise, move current to current.right.
  5. When the loop ends, current is null and parent is the node that should adopt the new node.
  6. If val < parent.val, set parent.left = new node.
  7. Otherwise, set parent.right = new node.
  8. Return the original root.

Code

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* newNode = new TreeNode(val);

        if (root == nullptr) {
            return newNode;
        }

        TreeNode* current = root;
        TreeNode* parent = nullptr;

        while (current != nullptr) {
            parent = current;
            if (val < current->val) {
                current = current->left;
            } else {
                current = current->right;
            }
        }

        if (val < parent->val) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }

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

        if root is None:
            return new_node

        current = root
        parent = None

        while current is not None:
            parent = current
            if val < current.val:
                current = current.left
            else:
                current = current.right

        if val < parent.val:
            parent.left = new_node
        else:
            parent.right = new_node

        return root
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode newNode = new TreeNode(val);

        if (root == null) {
            return newNode;
        }

        TreeNode current = root;
        TreeNode parent = null;

        while (current != null) {
            parent = current;
            if (val < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        if (val < parent.val) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        return root;
    }
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the tree

We traverse a single root-to-leaf path, making one comparison per level. For a balanced BST with n nodes, h ≈ log n, giving O(log n). For a completely skewed BST, h = n, giving O(n) in the worst case. This is the same time complexity as the recursive approach — the fundamental work is identical.

Space Complexity: O(1)

We use only two pointer variables (current and parent) and one new node, regardless of the tree size. No recursion stack, no auxiliary data structures. This is the key advantage over the recursive approach, which uses O(h) stack space. For a skewed tree with 10,000 nodes, this saves 10,000 stack frames.