Insert Into BST
01 · Problem
You are given the root of a binary search tree (BST) with distinct values and an integer val that is not already in the tree. Insert val as a new leaf at the position where a standard BST search for val would fall off the tree, and return the root.
Start at the root; move left when val is smaller than the current node and right when it is larger, until you reach an empty child slot. Do not rebalance or restructure any existing nodes. If the tree is empty, the new node becomes the root. Trees are given and returned in level-order form, with null marking missing children (trailing nulls omitted).
02 · Examples
root = [4,2,7,1,3], val = 5
[4,2,7,1,3,5]
5 > 4 goes right to 7; 5 < 7 goes left, which is empty, so 5 becomes the left child of 7.
root = [40,20,60,10,30,50,70], val = 25
[40,20,60,10,30,50,70,null,null,25]
25 < 40 goes left to 20; 25 > 20 goes right to 30; 25 < 30 goes left, which is empty, so 25 becomes the left child of 30.
root = [], val = 5
[5]
The tree is empty, so the new node is the root.
03 · Constraints
- 01The number of nodes in the tree is in the range [0, 104].
- 02-108 <= Node.val <= 108
- 03All node values are unique, and val does not already exist in the tree.
- 04-108 <= val <= 108
- 05The input tree is a valid binary search tree.
04 · Optimal complexity
- Time
- O(h)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.