class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) return new TreeNode(val);
        TreeNode* prev = nullptr;
        for (auto node = root; node != nullptr; ) {
            prev = node;
            node = val < node->val ? node->left : node->right;
        }
        auto destination = val < prev->val ? &prev->left : &prev->right;
        *destination = new TreeNode(val);
        return root;
    }
};