[Leetcode 701] Insert into a Binary Search Tree

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store