465. Insert into a Binary Search Tree
Your function receives the root of a binary search tree (possibly empty) and an integer val that is guaranteed not to appear in the tree. Attach val to the tree as a new leaf, keeping the BST ordering rule intact (every node's left subtree holds smaller values, its right subtree larger ones), and return the root of the updated tree.
Insert at the standard leaf position: starting from the root, go left when val is smaller than the current node and right when it is larger, and attach the new node where you fall off the tree. This makes the resulting tree unique, and the judge compares against exactly that tree.
The tree arrives as a level-order listing with null marking absent children; your answer is checked by the level-order traversal of the tree you return (missing children simply skipped).
Example 1:
Input: root = [4, 2, 7, 1, 3], val = 5
Output: [4, 2, 7, 1, 3, 5]
Explanation: 5 is greater than 4 (go right) and smaller than 7 (go left) — 7 has no left child, so 5 becomes 7's left leaf.
Example 2:
Input: root = [40, 20, 60, 10, 30, 50, 70], val = 25
Output: [40, 20, 60, 10, 30, 50, 70, 25]
Explanation: 25 walks left of 40, right of 20, left of 30, and lands as 30's left leaf.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- -10⁸ ≤ Node.val, val ≤ 10⁸
- All values in the tree are distinct, and val is not among them.
Hints:
The BST rule tells you which way to go at every node: val < node.val means the new value must live somewhere in the left subtree, otherwise in the right one. You never need to look at more than one child.
Walk down until the side you need to go to is empty — that empty spot is exactly where the new leaf belongs. Handle the empty tree first: the new node simply becomes the root.
Recursively: insert into the proper child subtree and reassign that child pointer with the returned root (root.left = insert(root.left, val)). Iteratively: remember the parent as you descend and attach to it at the end — same O(h) walk, no call stack.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [4, 2, 7, 1, 3], val = 5
Expected output: [4, 2, 7, 1, 3, 5]