You are given a binary search tree (BST) and a number val that is not in the tree yet. Insert val into the tree and return the tree after the insertion.
Which tree to return: there are many valid ways to insert a value, and the judge compares your answer with one fixed tree. Use the simplest way: start at the root and walk down. Go left if val is smaller than the current node, and right if it is bigger. When you reach an empty place, put val there as a new leaf.
How the judge passes the data
Examples
Example 1:
Input: root = [10,5,15,3,7,12,18], val = 6
Output: [10,5,15,3,7,12,18,null,null,6]
Explanation: 6 is smaller than 10, bigger than 5, smaller than 7. It becomes the left child of 7.
Example 2:
Input: root = [8,3,10], val = 14
Output: [8,3,10,null,null,null,14]
Explanation: 14 is bigger than 8 and bigger than 10. It becomes the right child of 10.
Example 3:
Input: root = [], val = 7
Output: [7]
Explanation: The tree is empty, so 7 becomes the root.