DSA problem
Insert into a Binary Search Tree
You are given the root of a binary search tree and a value val to insert. Return the root of the BST after inserting a new node with value val. The input data is guaranteed such that the new value does not already exist in the original BST. Multiple valid insertions exist; any structurally valid BST is accepted.
A new value is always inserted at a leaf position. The BST ordering invariant tells you exactly where: starting from the root, descend left when val < node.val and right when val > node.val, repeating until you walk off the tree. That null spot is the only legal place for the new node.
A recursive formulation is concise — insert returns a tree whose subtree at the appropriate slot has been replaced — but it uses O(h) stack space. An iterative descent avoids that overhead by tracking a parent pointer alongside the walking pointer, then attaching the new node as either the parent's left or right child when the walk falls off.
The optimal solution walks a single pointer down the tree, remembering its parent. When the pointer becomes null, allocate a new node with value val, attach it under the parent on the appropriate side, and return the (unchanged) root. Special case: if the input root is null, return a fresh node as the new root. The algorithm runs in O(h) time and O(1) extra space.
Examples
root = [4,2,7,1,3], val = 5[4,2,7,1,3,5]root = [40,20,60,10,30,50,70], val = 25[40,20,60,10,30,50,70,null,null,25]root = [], val = 5[5]Constraints
- The number of nodes in the tree will be in the range [0, 10^4].
- -10^8 <= Node.val <= 10^8
- All the values Node.val are unique.
- -10^8 <= val <= 10^8
- It is guaranteed that val does not exist in the original BST.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.