Add a New Key to a Search Tree
Implement insertKey
You are given the root of a binary search tree with distinct values and a key that is not yet in the tree. Insert the key as a new leaf, at the position where a search for the key would have ended, so the tree remains a valid binary search tree. Every existing node keeps its place. Return the root of the resulting tree.
You could rebuild the whole tree from a list of its values, but a single walk down the search path finds the empty slot directly.
Example 1:
Input: root = [45,25,65,15,35,55,75], key = 40
Output: [45,25,65,15,35,55,75,null,null,null,40]
Example 2:
Input: root = [45,25,65,15,35,55,75], key = 5
Output: [45,25,65,15,35,55,75,5]
Example 3:
Input: root = [], key = 8
Output: [8]
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ●
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node (null for an empty tree) - ●
key is a value between 0 and 1000 that is NOT already in the tree - ●
Insert key as a NEW LEAF at the position where a search for it would have ended, keeping every other node where it is. Return the root of the resulting tree (checked as a level-order list)
root =
key =