Recursive:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root){
return new TreeNode(val);
}
if(root->val < val){
root->right = insertIntoBST(root->right, val);
}
else{
root->left = insertIntoBST(root->left, val);
}
return root;
}
Iterative:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root){
return new TreeNode(val);
}
TreeNode *cur = root;
while(cur){
if(cur->val < val){
if(cur->right == NULL){
cur->right = new TreeNode(val);
break;
}
else{
cur = cur->right;
}
}
else{
if(cur->left == NULL){
cur->left = new TreeNode(val);
break;
}
else{
cur = cur->left;
}
}
}
return root;
}
