We have a valid binary search tree, and we need to insert a new value into it while keeping the BST property intact. The BST property says that for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

We don't need to restructure the tree. Since the value doesn't already exist in the BST, there's always an empty spot (a null position) where this value belongs. We find that spot by following the same comparison logic we'd use to search for a value, then attach a new node there.

The problem says multiple valid answers exist because we could insert the value at different positions and still maintain a valid BST. Inserting it as a new leaf node at the correct position is the approach we'll use, and it requires no rebalancing.

Key Constraints:

Intuition

Insertion follows the same path as searching for a value. We walk down the tree making left or right decisions based on comparisons, and when we reach a null child, that is where the new node goes.

If the tree is empty, the new node becomes the root. Otherwise, compare the value with the current node. If it is smaller, the value belongs in the left subtree; if it is larger, it belongs in the right subtree. Recurse into that subtree until reaching a null position, then create and return a new node there.

The recursive call returns the node for each subtree, and the parent links to it through the assignment root.left = insertIntoBST(root.left, val) (or the right-side equivalent). For an existing subtree this assignment is a no-op because the call returns the same node; for the null position it wires in the new leaf.

Algorithm

Visualization and Code

The recursion only moves in one direction at each step and never backtracks, so the call stack stores nothing the work depends on. An iterative version removes the O(h) stack space.

Intuition

We use a pointer to walk down the tree, comparing at each node and going left or right. The difference from recursion is the linking step. The recursive version reattaches the child through its return value, so the parent link is restored on the way back up. The iterative version has no return value to lean on, so it stops one level early: instead of stepping onto a null child, it detects that the child is null, attaches the new node there directly, and returns.

This works because the BST property fixes a single path from the root to the null position. At each node, comparing val against current.val decides the direction with no ambiguity, and the value is guaranteed not to already exist, so the walk always ends at a null child rather than at a matching node.

Algorithm

Visualization and Code