Insert a value into a binary search tree and return the updated root.
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:
The tree may be empty.
root: root node of a binary search tree, or nullval: integer value to insertrootvalExample 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
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.