361. Insert a given node in BST
Given the root node of a binary search tree (BST) and a value val to insert into the tree. Return the root node of the BST after the insertion.
It is guaranteed that the new value does not exist in the original BST. Note that the compiler output shows true if the node is added correctly, else false.
Example 1:
Input : root = [4, 2, 7, 1, 3] , val = 5
Output : [4, 2, 7, 1, 3, 5]
Explanation :
Below is image where the node 5 is inserted
There is another way to insert the given val as shown below.
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 :
Below is image where the node 25 is inserted
Now Your Turn!
Pick the correct output for the given inputInput : root = [4, 2, 7, 1, null, 6] , val = 3
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= Number of nodes <= 104
- -108 <= Node.val <= 108
- All values in tree are unique.
- -108 <= val <= 108
- It is guaranteed that the val does not exists in original BST.