502. Grow the Search Tree
A library catalogue is stored as a binary search tree of shelf numbers: keys in a node's left subtree are smaller, keys in its right subtree are larger, and all keys are distinct. A new shelf with number value, which is not yet in the tree, has to be added.
Insert it as a brand new leaf without moving, removing or re-linking any existing node: start at root, go left when value is smaller than the current key and right otherwise, and attach the new node at the first empty position you reach. Return the root of the resulting tree. If root is empty, the answer is a tree holding only the new node.
Example 1
- Input:
- root = [8,3,12,1,5,10,14], value = 6
- Output:
- [8,3,12,1,5,10,14,null,null,null,6]
- Explanation:
6 is larger than 3 and larger than 5, so it becomes the right child of 5.
Example 2
- Input:
- root = [8,3,12,1,5,10,14], value = 13
- Output:
- [8,3,12,1,5,10,14,null,null,null,null,null,null,13]
- Explanation:
Descending 8, 12, 14 ends at the empty left slot of 14, where 13 is attached.
Constraints
0 ≤ number of nodes ≤ 104
-231 ≤ Node.val, value ≤ 231 - 1
The tree is a valid binary search tree with distinct keys, and value does not occur in it.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h)
- Space
- O(1)