Insert a value into a binary search tree and return the updated root.
Insert Into a Binary Search Tree
You are given the root of a binary search tree (BST) and an integer val.
Insert val into the BST so that the tree remains a valid BST. If the value is already present, place the new node in a valid position according to BST insertion rules.
Return the root of the tree after insertion.
A BST follows these rules:
- All values in the left subtree are strictly smaller than the node's value.
- All values in the right subtree are strictly greater than the node's value.
The tree may be empty.
Input Format
root: root node of a binary search tree, ornullval: integer value to insert
Output Format
- Return the root of the BST after inserting the new value.
Constraints
- The tree contains at most one node with any given value.
- The resulting tree must satisfy the BST property.
- You may assume the input tree is a valid BST.
Hints
- Walk down the tree using the BST ordering property.
- You only need to change one pointer or create one new node.
- A recursive solution and an iterative solution are both natural here.
Input Format
- A binary search tree root node
root - An integer
val
Output Format
- The root node of the BST after insertion
Constraints
- Input is a valid BST
- The tree may be empty
- Preserve the BST property after insertion
Example 1
Input
root = [4,2,7,1,3], val = 5
Output
[4,2,7,1,3,5]
Explanation
5 is greater than 4, so move right to 7. Then 5 is smaller than 7, so insert it as the left child of 7.
Example 2
Input
root = [40,20,60,10,30,50,70], val = 25
Output
[40,20,60,10,30,50,70,null,null,25]
Explanation
25 goes left from 40, right from 20, and then becomes the left child of 30.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.