Insert into a Binary Search Tree
Asked at Anduril
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
The BST property tells you exactly where to go at each node: left if the value is smaller, right if it is larger.
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.
Iterative version: keep a pointer, move left/right until the next step would be null, then attach. It uses O(1) extra space.
Edge case: an empty tree — return the new node as the root.
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).
What Trips People Up in Real Interviews
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.
Solution Code
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 rootFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.