Baseline Binary Search Trees · Practice Problems O(h) · O(h)
A compliance office files every contract by value in a sorted tree, and a brand-new contract arrives that matches nothing on file. Rather than reorganizing the archive, the clerk walks the tree once — smaller goes left, larger goes right — until a corridor dead-ends, and hangs the new contract exactly there. The archive's shape grows by one leaf; nothing else moves.
Input: A binary search tree as a level-order array (null marks a missing child) and an integer val to insert. val does not already exist in the tree.
Output: Return the tree after insertion, serialized as a level-order array with trailing nulls trimmed.
0 <= number of nodes <= 10^5-10^9 <= node value, val <= 10^9All values are unique before and after insertionInput: {"tree":[4,2,7,1,3],"val":5}
Output: [4,2,7,1,3,5]
5 descends right of 4, left of 7, and becomes 7's left child.
Input: {"tree":[],"val":5}
Output: [5]
Inserting into an empty archive creates the root.