# [Leetcode 701] Insert into a Binary Search Tree

**Description:**

You are given the `root`

node of a binary search tree (BST) and a `value`

to insert into the tree. Return *the root node of the BST after the insertion*. It is **guaranteed** that the new value does not exist in the original BST.

**Notice** that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return **any of them**.

**Example 1:**

**Input:** root = [4,2,7,1,3], val = 5

**Output:** [4,2,7,1,3,5]

**Explanation:** Another accepted tree is:

**Example 2:**

**Input:** root = [40,20,60,10,30,50,70], val = 25

**Output:** [40,20,60,10,30,50,70,null,null,25]

**Example 3:**

**Input:** root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

**Output:** [4,2,7,1,3,5]

**Constraints:**

- The number of nodes in the tree will be in the range
`[0, 104]`

. `-108 <= Node.val <= 108`

- All the values
`Node.val`

are**unique**. `-108 <= val <= 108`

- It’s
**guaranteed**that`val`

does not exist in the original BST.

**C code solution (recursive):**

`/**`

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){

struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

newNode->val = val;

newNode->left = NULL;

newNode->right = NULL;

if(!root){

return newNode;

}

if(val < root->val)

root->left = insertIntoBST(root->left, val);

else if(val > root->val)

root->right = insertIntoBST(root->right, val);

return root;

}

**C code solution (iterative):**

`struct TreeNode* insertIntoBST(struct TreeNode* root, int val){`

struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

newNode->val = val;

newNode->left = NULL;

newNode->right = NULL;

if(!root){

return newNode;

}

struct TreeNode* prev;

struct TreeNode* curr = root;

int is_left = 0;

//trace to the bottom node

while(curr){

if(val < curr->val){

prev = curr;

curr = curr->left;

is_left = 1;

}

else{

prev = curr;

curr = curr->right;

is_left = 0;

}

}

//decide the node should be at left or right of the bottom node

if(is_left)

prev->left = newNode;

else

prev->right = newNode;

return root;

}

**A very clean code solution:**

`struct TreeNode* insertIntoBST(struct TreeNode* root, int val){`

struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

newNode->val = val;

newNode->left = NULL;

newNode->right = NULL;

if(!root){

return newNode;

}

struct TreeNode** pp = &root;

while (*pp != NULL) {

if (val > (*pp)->val)

pp = &(*pp)->right;

else

pp = &(*pp)->left;

}

*pp = newNode;

return root;

}