DSA interview question

Insert a Node into a BST

Medium · Algorithms · Topics: bst, recursion

The problem

A leaderboard keeps scores in a binary search tree, and each new score must be inserted so that the tree stays a valid BST. The new key always ends up as a leaf. Walk down as if searching for it (left if it's smaller than the node, right if it's larger), and attach the new node at the first empty spot. No existing node moves, and the walk takes O(h).

Example: BST [4, 2, 7, 1, 3], insert 5 → [4, 2, 7, 1, 3, 5].

Function signature

TreeNode* insertIntoBST(TreeNode* root, int val);  // val is not already in the tree

Test cases

Input `(tree, val)`	Output (level order)	Explanation
`([4, 2, 7, 1, 3], 5)`	`[4, 2, 7, 1, 3, 5]`	5 becomes 7's left child
`([40, 20, 60, 10, 30, 50, 70], 25)`	`[40, 20, 60, 10, 30, 50, 70, null, null, 25]`
`([4, 2, 7, 1, 3], 0)`	`[4, 2, 7, 1, 3, null, null, 0]`	The new minimum
`([5], 6)`	`[5, null, 6]`
`([], 5)`	`[5]`	Empty tree

(Confirm: keys are distinct; any valid BST is accepted, and the leaf-insertion result is shown.)

How interviewers phrase it

"Given the root of a BST and a value to insert, insert it and return the root" (LeetCode 701).

Clarifying questions to ask

Is the value guaranteed not to exist? (Yes.)
Must the tree stay balanced? (No: plain BST insertion.)
Recursive or iterative? (Either; iterative avoids stack depth.)

Follow-ups to expect

"Why is the new node always a leaf?"
"What if the tree is empty?"
"Worst case?"
"How would duplicates be handled?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview