BST 插入：新结点一定成为叶子

BSTNode *bst_insert(BSTNode *root, int key) {
    // parent 记录 current 的父结点，最后用它挂接新叶子。
    BSTNode *parent = NULL;
    BSTNode *current = root;

    while (current != NULL) {
        parent = current;

        // 约定不插入重复关键字；原树不变，仍返回原根。
        if (key == current->key) {
            return root;
        }

        // 插入位置沿查找路径向下定位。
        if (key < current->key) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    // current 为 NULL，说明 parent 的某个空孩子就是插入位置。
    BSTNode *node = new_node(key);
    if (node == NULL) {
        return root;
    }

    if (parent == NULL) {
        // 原树为空，新结点就是整棵树的新根。
        return node;
    }

    if (key < parent->key) {
        parent->left = node;
    } else {
        parent->right = node;
    }

    return root;
}