struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

void insert(TreeNode*& root, int key) {
if (!root) {
root = new TreeNode(key);
return;
}
_______________________________
}