Insert into a Binary Search Tree
Medium · Trees · Tree · Binary Search Tree · Binary Tree
Problem
You are given the root of a binary search tree and a value val that does not already appear in the tree. Insert val and return the root of the updated tree.
Insert it the standard way, as a new leaf: walk down from the root, going left when val is smaller than the current node and right when it is larger, and place the new node in the first empty child slot you reach. Every original node keeps its place, and the tree stays a valid binary search tree.
(Other valid trees exist, for example after rebalancing, but the tests check this leaf insertion, which has exactly one answer.)
Examples
Input: root = [10,5,15,3,7], val = 12 Output: [10,5,15,3,7,12]
12 goes right of 10 and then left of 15, as a new leaf.
Input: root = [], val = 9 Output: [9]
Inserting into an empty tree creates the root.
Input: root = [40,20,60,10,30,50,70], val = 25 Output: [40,20,60,10,30,50,70,None,None,25]
25 goes left of 40, right of 20, then left of 30.
Constraints
- 0 <= number of nodes <= 10^4
- -10^8 <= Node.val, val <= 10^8
- All values, including val, are distinct
- root is a valid binary search tree
Approaches
- Recursive descent — time O(h), space O(h) for the call stack
Follow-up
Plain leaf insertion can build a chain when values arrive in sorted order, making every operation O(n). Self-balancing trees (AVL, red-black) add rotations after the insertion to keep the height O(log n). See the use cases for the floor and ceiling of a value and for building a whole tree by repeated insertion.
Related problems
Start free on Cariara · Coding problems · System design studio
