L43. Insert a given Node in Binary Search Tree | BST | C++ | Java

#treeSeries #striver #placements

[takeUforward]

Please likeeee, shareeee and :) Also follow me at Insta: Striver_79

[sibasish.tripathy]

Recursive Solution:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root) return new TreeNode(val);
if(val>root->val) root->right=insertIntoBST(root->right, val);
if(val<root->val) root->left=insertIntoBST(root->left, val);
return root;
}

[Kshitijsingh-nf]

MY APPROACH--

1->first traverse to find the correct location of our node
2->simultaneously keep track of the last node visited before our curr becomes null
3->lastvisited pos will be our correct pos to insert our node
4->we now just need to check wheter to put it on right or left, we do this by doing simple checks at end

TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
return new TreeNode(val);
}

TreeNode* curr = root;
TreeNode* lastVisited = NULL;

while (curr) {
lastVisited = curr;
if (val > curr->val) {
curr = curr->right;
} else {
curr = curr->left;
}
}

TreeNode* newNode = new TreeNode(val);

if (val > lastVisited->val) {
lastVisited->right = newNode;
} else {
lastVisited->left = newNode;
}

return root;
}

[krishnasudan]

I solved this by myself using ceil of binary tree concept.

But your approach was amazing. Thanks striver. 😊😊😊😊

[aakriti]

At line no. 7 in C++ code,
if(cur->val <= val)

Here, equal to is not required in the condition, right?

Because the value which we want to insert in the Binary Search Tree will never be equal to any node's value in the tree as per the question, "It is guaranteed that the new value does not exist in the original BST".

[akashyadav]

Recursion : if anyone likes
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root == NULL){
return new TreeNode(val);
}
if(val<root->val){
root->left = insertIntoBST(root->left, val);
}else{
root->right = insertIntoBST(root->right, val);
}
return root;
}

[aakashgoswami]

Iterative approach .More simpler code:
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root)return new TreeNode(val);
TreeNode* prev = NULL;
TreeNode* newRoot = root;
while(root){
if(root->val<val){
prev = root;
root = root->right;
}else{
prev = root;
root = root->left;
}
}
if(prev->val>val)prev->left = new TreeNode(val);
else prev->right = new TreeNode(val);
return newRoot;
}
};

[shivangisrivastava]

For real! i could solve this medium ques with the exact same logic as yours! I think this should be tagged easy on LC. <3 Striver

[everythinguneed]

class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null)
{
return new TreeNode(val);
}

// Movement in the BST
if(root.val<val)
{
root.right = insertIntoBST(root.right, val);
}
else
{
root.left = insertIntoBST(root.left, val);
}

return root;
}
}

[judgebot]

tbh it isn't quite odd that there is always a valid way of adding a node at leaf node in case of BST. I was expecting some algo that modifies root itself!!

[AbhishekKumar-qyek]

Sir you are the best. Thankyou for this video. Forever grateful.

[pragmaticcoder]

Thanks for explaining this in Java. I really need this to understand BSTs

[techmatein]

I used the same approach as of your's without continuing the video, 🥳

[hareshnayak]

Understood, thanks striver for this amazing video .

[saurabhgautam]

Thanktou bhaiya, actually thankyou is not enough, but because of your support I m able to solve problem on my own

[RahulKumar_gr]

A height balanced BST is nothing but a AVL tree.

for AVL trees the TC is OlogN
For BST the worst case TC is O(n) in case of skewed tree
Anyways the TC is O(height of tree)

[ashwanisharma]

Thank you for the video! It was really helpful and informative. I appreciate the time and effort that you put into creating it. Your expertise and knowledge on the subject really shine through, and I learned a lot from watching it.😊

[mihirsaini]

Great explanation as always! Hats off to your efforts

[tav]

Thank you so much for all these videos striver you are the goat im going to share your channel with all my freinds

[utkarsh_]

is it necessary that all the new nodes come into the leaf? what about cases where it's not?