Insert into a binary search tree

Given the root of a binary search tree and a value not already in it, insert the value and return the root of the tree.

Before you code

The new value goes exactly where a search for it would fall off the tree. Write it in the return-the-subtree-root style, and the empty tree needs no special case.

Hints

1. insert(None, val) returns a new node.
2. Otherwise recurse left or right and assign the result back to node.left or node.right, then return node.
3. Iterative version: walk down remembering the parent, then attach the new node to the correct side of the parent.

Production & complexity notes

When solving Insert into a binary search tree on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Insert and delete to reinforce the underlying pattern.

What it practices

Insertion as a search plus one link, from Insert and delete.