Insert into a Binary Search Tree
You are given the root of a binary tree. Insert val into the BST and return the root. Do it the simple way: walk down from the root, going left when val is smaller than the node and right when it is larger, and attach a new leaf where you fall off the tree. Do not rearrange existing nodes. val is not already in the tree. If the tree is empty, the new node is the root. In a binary search tree every value in a left subtree is smaller than its node and every value in a right subtree is larger.
Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.
Example 1
5 goes right of 4, then left of 7: the tree becomes [4,2,7,1,3,5].
Constraints
0 <= number of nodes <= 100-1000 <= node.val <= 1000- The tree is a valid binary search tree.
-1000 <= val <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.