#701 Insert into a Binary Search Tree
frequently reported atMicrosoftAmazonGoogleLinkedInBloomberg
the problem
In plain words
Insert val (guaranteed not already present) into the BST and return the root. Any valid BST is accepted.
in root = [4,2,7,1,3], val = 5
out [4,2,7,1,3,5]
5 > 4 → right; 5 < 7 → left of 7, which is empty.
in root = [], val = 5
out [5]
- 0 ≤ number of nodes ≤ 10⁴
- -10⁸ ≤ Node.val, val ≤ 10⁸
- All values unique; val is new
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBST property
Search for val. Where the search falls off the tree is the only spot that keeps every ancestor's rule true — attach it there as a leaf.
solutions
From brute force to optimal
Collect sorted values, insert val in the list, build a balanced BST.
- Inorder into a list.
- Binary-search the insertion point and add.
- Middle-as-root rebuild.
Touches every node twice.
The list and a new tree.
class Solution { /** Collect sorted values, add val, rebuild a balanced BST. Correct but wasteful. */ public TreeNode insertIntoBST(TreeNode root, int val) { List<Integer> values = new ArrayList<>(); collect(root, values); int pos = Collections.binarySearch(values, val); values.add(-pos - 1, val); // insertion point keeps the list sorted return build(values, 0, values.size() - 1); } private void collect(TreeNode node, List<Integer> out) { if (node == null) return; collect(node.left, out); out.add(node.val); collect(node.right, out); } private TreeNode build(List<Integer> values, int lo, int hi) { if (lo > hi) return null; int mid = lo + (hi - lo) / 2; return new TreeNode(values.get(mid), build(values, lo, mid - 1), build(values, mid + 1, hi)); }}Insert into the correct subtree and re-link the returned root.
- null → new node.
- Recurse left or right; assign the result back.
- Return root.
One path down.
Recursion stack.
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); // found the empty spot if (val < root.val) root.left = insertIntoBST(root.left, val); else root.right = insertIntoBST(root.right, val); return root; // re-link: unchanged above the new leaf }}Walk down with a pointer; when the next step is null, attach.
- Empty tree → return the new node.
- Walk left/right; attach when the child slot is null.
- Return the original root.
One path down.
Only a pointer and the new node.
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { TreeNode fresh = new TreeNode(val); if (root == null) return fresh; TreeNode cur = root; while (true) { if (val < cur.val) { if (cur.left == null) { cur.left = fresh; break; } cur = cur.left; } else { if (cur.right == null) { cur.right = fresh; break; } cur = cur.right; } } return root; }}Dry run
in the room
How to say it in the interview
talk track
- Say why a leaf is always enough: the search path is exactly the list of ancestors whose rules the new value must obey.
- Point out that the original root is returned unchanged (unless the tree was empty).
traps
- Forgetting the empty-tree case.
- Recursive version: calling
insertIntoBST(root.left, val)without assigning it back toroot.left.
what they ask next
Follow-ups
Keep it balanced?
That's what AVL/red-black trees do with rotations after each insert. In Java, just use TreeSet.
before you submit
Edge cases to test
- Empty tree → the new node is the root.
- val smaller than everything → it becomes the left child of the leftmost node.
- A right-skewed tree (built from sorted inserts) → the walk is O(n), and a recursive version is n calls deep.
practise next
Similar problems
- #700Search in a Binary Search TreeEasyin BST
- #450Delete Node in a BSTMediumin BST
- #108