# [Leetcode 701] Insert into a Binary Search Tree

`Input: root = [4,2,7,1,3], val = 5Output: [4,2,7,1,3,5]Explanation: Another accepted tree is:`
`Input: root = [40,20,60,10,30,50,70], val = 25Output: [40,20,60,10,30,50,70,null,null,25]`
`Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5Output: [4,2,7,1,3,5]`
`/** * 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;}`
`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;}`
`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;}`

--

--