Given the root of a BST and a value to insert, insert the value into the BST and return the root of the resulting tree. There may be multiple valid trees — return any of them that preserves the BST property.
Example 1
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: 5 > 4, go right to 7; 5 < 7, go left — 7 has no left child, so 5 is attached there.
1 <= number of nodes <= 10^4-10^8 <= Node.val, val <= 10^8All values are uniqueA BST's sorted-order property tells you exactly which direction to go at every node — no need to search both subtrees.
The insertion point is always a leaf position — you're not rearranging the tree, just attaching one new node where a null child currently is.
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val); // found the correct empty spot
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}Time: O(h), h = tree height (O(log n) balanced, O(n) worst case) · Space: O(h)