360. Insert Into a Search Tree
The tree is a binary search tree. Insert the value x into it, then print the
inorder traversal of the result.
Insertion is the search from problem 331 that does not stop. Walk down as though
looking for x, and when you reach a missing child, that is where the new node
belongs. Nothing else moves.
If x is already present, change nothing and print the tree as it stands.
The check on your work is built in: the output must come out sorted, because it is an inorder traversal of a search tree. If it does not, the insertion went to the wrong place.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value, x ≤ 1000000000` - All existing values are distinct and the tree is a valid search tree.
Input
The first line contains two integers n and x.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root, and the tree is a search tree.
Output
Print the inorder traversal after inserting x, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.