Insert into BST
Mediumjavapythonccppjavascript
Insert a new value into a Binary Search Tree, following the usual BST rule (smaller values go left, larger go right), and print the resulting tree.
The result is printed in canonical level-order form: a breadth-first walk emitting each value and null for a real node's missing child, with trailing null tokens removed.
Input Format
The first line contains an integer M. The second line contains M space-separated tokens (integers or null) — the BST in level order. The third line contains the integer X to insert.
Output Format
Print the canonical level-order serialization of the BST after the insertion.
Example 1
Input
3 8 3 10 6
Output
8 3 10 null 6
Explanation: 6 < 8 and 6 > 3, so it becomes the right child of 3.
- 1 <= number of nodes <= 5000
- The value X does not already exist.
- -1000000000 <= value, X <= 1000000000