Given the root of a binary search tree with distinct values (smaller values on the left, larger on the right) and a value val that is not yet in the tree, insert a new node holding val in the position that keeps the tree a valid search tree and does not move any existing node. Return the root.
Examples
5 5
/ \ / \
3 8 ==> 3 8
/ \ / \ /
1 4 1 4 7
Input: root = build_tree([5, 3, 8, 1, 4]), val = 7
Output: tree_to_list(...) == [5, 3, 8, 1, 4, 7]
Input: root = build_tree([]), val = 7
Output: [7]
Constraints
0 <= number of nodes <= 1000-10**4 <= node.val, val <= 10**4, all distinct
Goals
- Use the ordering property to choose a direction at every node
- Attach a new node by returning it from the recursion