Add a New Key While Preserving Search-Tree Order
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Insert val, which is absent, into a binary search tree and return the resulting root pointer. Preserve the original values and add val once. Any resulting BST satisfying this insertion contract is accepted; its shape need not be unique. TreeNode remains the native interface.
```cpp
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val);
};
```
### Examples
**Example 1:**
```text
root = [6,3,9], val = 7
One valid output: [6,3,9,null,null,7]
Explanation: Attach 7 as the left child of 9.
```
**Example 2:**
```text
root = [], val = -2
Output: [-2]
Explanation: The new node becomes the root.
```
### Constraints
- Before insertion there are 0 through 10000 nodes.
- Node values and the new key lie in [-100000000,100000000].
- Existing keys are pairwise distinct, and val is absent.
### Contract considerations
Return TreeNode*, allow a new root for an empty tree, and accept source-supported output shape freedom.
```hint Read the boundary condition
Where does a failed search for the absent value end?
```
### What a Strong Answer Covers
Return TreeNode*, allow a new root for an empty tree, and accept source-supported output shape freedom.
### Follow-up Questions
Optional practice extension: How would maintaining balance affect the worst-case height and insertion cost?
Overview: Add a New Key While Preserving Search-Tree Order. Insert val, which is absent, into a binary search tree and return the resulting root pointer.