MediumTreeBinary Search TreeBinary TreeUpdated Sep 2026

701. Insert into a Binary Search Tree

Asked at Anduril

Difficulty

Medium

Time

O(h)

Space

O(1)

Pattern

Tree

Companies

1

Problem

You are given the root of a binary search tree (BST) and a value val. Insert val into the tree and return the root of the resulting tree.

A BST has this rule at every node: all values in the left subtree are smaller, and all values in the right subtree are larger. The value val is guaranteed not to be in the tree already.

There are many correct answers. Any tree that still follows the BST rule after the insert is accepted. The easiest valid answer is to walk down the tree using the BST rule and attach the new value as a leaf at the first empty spot you reach.

Where does 5 belong?

12345 > 4 → go right75 < 7 → go leftFollow the comparisons from the root down to an emptychild slot.123457Attach 5 as the left child of 7 — the tree is still avalid BST.
The BST rule sends 5 right of 4 and left of 7, and 7 has no left child, so 5 lands there.

Constraints

  • ●The number of nodes in the tree is in the range [0, 10^4].
  • ●-10^8 <= Node.val <= 10^8.
  • ●All node values are unique.
  • ●-10^8 <= val <= 10^8.
  • ●val is guaranteed not to exist in the original BST.

Examples

Example 1
Inputroot = [4,2,7,1,3], val = 5
Output[4,2,7,1,3,5]
WhyStart at 4: 5 is bigger, so go right to 7. At 7, 5 is smaller and 7 has no left child, so we attach 5 as the left child of 7.
Example 2
Inputroot = [40,20,60,10,30,50,70], val = 25
Output[40,20,60,10,30,50,70,null,null,25]
Why25 < 40 go left to 20; 25 > 20 go right to 30; 25 < 30 and 30 has no left child, so 25 becomes the left child of 30.
Example 3
Inputroot = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output[4,2,7,1,3,5]
WhySame path as the first example: 5 goes right of 4, then left of 7. The extra nulls in the input are just empty children.

Asked At

1 companies
CompanyDifficulty
AndurilMediumView all Anduril questions →

How to Think About It

1

The BST property tells you exactly where to go at each node: left if the value is smaller, right if it is larger.

2

Key insight: you never need to restructure the tree. Walk down until the child pointer you want to follow is null, and hang the new node there as a leaf.

3

Iterative version: keep a pointer, move left/right until the next step would be null, then attach. It uses O(1) extra space.

4

Edge case: an empty tree — return the new node as the root.

5

Walkthrough: insert 5 into [4,2,7,1,3]: 5 > 4 go right to 7; 5 < 7 and 7 has no left child -> attach 5 as the left child of 7.

Optimal Approach

Step 1: If root is null, return a new node with val.
Step 2: node = root.
Step 3: Loop:
If val < node.val: if node.left is null, attach and stop; else node = node.left.
Else: if node.right is null, attach and stop; else node = node.right.
Step 4: Return root.

Time: O(h). Space: O(1).

Walk down, then attach

1234node = 47Start at the root. Compare val with node.val.12347node = 7, left is null5 > 4, so move right. Now node is 7 and 7.left is empty.1234577.left = new node(5)Attach the new node and return the original root.if val < node.val: go leftelse: go rightattach when the child is null
Keep one pointer and move left or right until the next step would be null, then hang the new leaf there.
ComplexityTime O(h)Space O(1)We follow one root-to-leaf path, so the cost is the tree height h; the iterative version needs no extra memory.

What Trips People Up in Real Interviews

1

Trying to insert in the middle and rebalance. Any valid BST is accepted — a new leaf is the simplest correct answer.

2

Returning the new node instead of the original root when the tree is not empty.

3

Forgetting the empty-tree case.

4

Claiming O(log n) unconditionally. It is O(h), which is O(n) for a skewed tree.

Solution Code

O(h) time
def insertIntoBST(root, val):
    if not root:
        return TreeNode(val)
    node = root
    while True:
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
                break
            node = node.left
        else:
            if not node.right:
                node.right = TreeNode(val)
                break
            node = node.right
    return root

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Insert into a Binary Search Tree problem?

Insert into a Binary Search Tree asks you to insert a new value (guaranteed not to exist yet) into a BST and return the root. Any valid BST is accepted, and the simplest valid answer is to walk down to the right empty spot and attach a new leaf there.

How do you solve Insert into a Binary Search Tree?

The optimal approach runs in O(h) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Insert into a Binary Search Tree?

Insert into a Binary Search Tree is asked at Anduril. It is a medium difficulty problem.

What are common mistakes on Insert into a Binary Search Tree?
  • Trying to insert in the middle and rebalance. Any valid BST is accepted — a new leaf is the simplest correct answer.
  • Returning the new node instead of the original root when the tree is not empty.
  • Forgetting the empty-tree case.
  • Claiming `O(log n)` unconditionally. It is `O(h)`, which is `O(n)` for a skewed tree.