876. Insert into Binary Search Tree

Given the root of a binary search tree and a value to insert (guaranteed not already present), insert it as a new leaf maintaining the BST property, and return the resulting tree as a level-order array. The standard insertion descends to the correct empty spot. The input gives a level-order BST array and the value separated by ' | '.

Input: A level-order BST array and the value, separated by ' | '.

Output: Array — the resulting BST in level order.

Examples

Input: [4,2,7,1,3] | 5
Output: [4,2,7,1,3,5]
Explanation: 5 becomes the left child of 7.

Input: [] | 5
Output: [5]
Explanation: Insert into an empty tree.

Input: [5] | 3
Output: [5,3]
Explanation: 3 becomes the left child.

Constraints

• 0<=nodes<=10^4
• valid BST
• value not present

Asked by