Insert into a Binary Search Tree

To solve this efficiently at Netflix, I would first confirm the constraints regarding duplicates, as our systems often require unique keys. Assuming standard BST rules where duplicates go to the right, I'd choose an iterative approach to avoid stack overflow risks with deep trees, though recursion is also acceptable for moderate depths. My logic starts at the root. If the tree is empty, the new node becomes the root. Otherwise, I traverse down: if the new value is less than the current node, I move left; if greater, I move right. I continue this loop until I encounter a null pointer. At that exact spot, I allocate memory for the new node and attach it as either the left or right child of the previous node. Finally, I return the original root reference to ensure the caller receives the updated tree structure. For example, inserting 5 into a tree rooted at 10 would move left to 5 (if exists) or insert there. This approach runs in O(h) time, where h is the height, and uses O(1) extra space iteratively, demonstrating both algorithmic efficiency and practical engineering judgment.