Delete a node from Binary Search Tree
Вставка
- Опубліковано 1 жов 2024
- See complete series on data structures here:
• Data structures
In this lesson, we have discussed deletion of a node from binary search tree data structure. We have discussed the core logic and written implementation of it in C++.
See source code here:
gist.github.co...
For practice problems and more, visit: www.mycodeschoo...
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool
Who's watching in 2024? :D
It's me
Me 🙋
me
"Woohoo I found you, get ready to be deleted" 😂😂😂
Bazingaaaa
@@devprakash5320 huhh..Sheldon
😂😂😂😂😂
XD
the op is dead
The number of lives this channel has touched is far far greater :)
Reason: In the year 2014 there were hardly any DSA channels on youtube This very channel inspired the entire generation of Data-Structures UA-cam Channel.
I have starting liking data structures after going through your videos.. Really appreciate !!!
Watching one hour ago from paper 😂😂
Even in 2021 when there are so many videos/playlists available on UA-cam, it's hard to find this much easily understandable and quality content on DSA. 😍
i agere
100% agreed
2022
I completed the playlist
Can you please recommend resources for studying next concepts like graph algos, dp, etc?
@@CuriousAnonDev Unfortunately one of the two people who started this channel is no more.He died in an accident in US and the other person wasnt in right state of mind for few days.I hope they r both fine in their own worlds now ....lots of love to their work
amazing how my college professors don't take the time out to explain it in depth as much as you do, truly appreciate it.
because they themeselves don't understand it in depth. what a sorry state
i believe, in some case that we don't pay that attention in the lectures
@@kannanhassouna5706 Or the lecturers are too boring and don't make the lessons interesting, at the end of the day we are humans and operate on emotions
//Function to find minimum in a tree.
Node* FindMin(Node* root)
{
while(root->left != NULL) root = root->left;
return root;
}
correct
but we are interested in finding maximum in left subtree or minimum in right subtree..and you are showing the overall minimum for an entire tree...
@@NEERAJKUMAR-db9se Every subtree is also a binary search tree
@@NEERAJKUMAR-db9se for function FindMin() Node* root is variable. We can use it for the right subtree as well.
return root->data
14:22 "i hope this is making sense"
my brain : farting
Glad i am not the only one lmao
@@kaus05 bro this shit just making my head like its gonna explosive
I have followed all your Data Structures videos, they are great! I love that you just dont explain the ADT but also show how to code it. That´s really helpful for somebody like me which still doesn't have lots of experience coding. Keep the good work! I'm waiting for your new videos to come out! =)
Code for BST in C is below.
#include
#include
#define TRUE 1
#define FALSE 0
struct Node
{
char data;
struct Node* left;
struct Node* right;
};
struct Queue
{
struct Node* bst;
struct Queue* next;
};
struct Queue* head;
struct Node* root;
struct Queue* Enque(struct Node* root)
{
struct Queue* temp1;
temp1 = (struct Queue*) malloc(sizeof(struct Queue));
temp1->bst = root;
temp1->next = NULL;
if(head==NULL)
head = temp1;
struct Queue* temp2;
temp2 = head;
while(temp2->next != NULL)
temp2 = temp2->next;
temp2->next = temp1;
temp1->next = NULL;
return head;
}
struct Node* Front()
{
return head->bst;
}
Deque()
{
struct Queue* temp1;
temp1 = head;
head = temp1->next;
free(temp1);
}
Empty()
{
if(head == NULL) return 1;
else return 0;
}
struct Node* GetNew(char c)
{
struct Node* New = (struct Node*) malloc(sizeof(struct Node));
New->data = c;
New->left = New->right = NULL;
return New;
}
struct Node* Insert(struct Node* root, char c)
{
if(root==NULL)
{
root = GetNew(c);
return root;
}
else if(c data)
{
root->left = Insert(root->left, c);
return root;
}
else
{
root->right = Insert(root->right, c);
return root;
}
}
int Search(struct Node* root, char c)
{
if(root == NULL)
return FALSE;
else if(root->data == c)
return TRUE;
else if(cdata)
return Search(root->left, c);
else return Search(root->right, c);
}
char Least(struct Node* root)
{
while(root->left != NULL)
root = root->left;
return root->data;
}
char Highest(struct Node* root)
{
while(root->right != NULL)
root = root->right;
return root->data;
}
int max(int a, int b)
{
if(a>b) return a;
else return b;
}
int Height(struct Node* root)
{
int LH = 0, RH = 0;
if(root == NULL)
return -1;
LH = LH + Height(root->left);
RH = RH + Height(root->right);
return max(LH, RH) + 1;
}
Level(struct Node* root)
{
if(root==NULL)
{
printf("Tree is empty.
");
return;
}
struct Node* temp;
struct Queue* head = NULL;
Enque(root);
while(!Empty())
{
temp = Front();
Deque();
printf("%c\t", temp->data);
if(temp->left != NULL) Enque(temp->left);
if(temp->right != NULL) Enque(temp->right);
}
}
Preorder(struct Node* root)
{
if(root == NULL) return;
printf("%c\t", root->data);
Preorder(root->left);
Preorder(root->right);
}
Inorder(struct Node* root)
{
if(root==NULL) return;
Inorder(root->left);
printf("%c\t", root->data);
Inorder(root->right);
}
Postorder(struct Node* root)
{
if(root==NULL) return;
Postorder(root->left);
Postorder(root->right);
printf("%c\t", root->data);
}
struct Node* Findmin(struct Node* root1)
{
if(root1==NULL) return root1;
while(root1->left != NULL)
root1 = root1->left;
return root1;
}
struct Node* Delete(struct Node* root, char d)
{
if(root==NULL) return root;
else if(ddata) root->left = Delete(root->left, d);
else if(d>root->data) root->right = Delete(root->right, d);
else
{
if((root->left==NULL) && (root->right==NULL))
{
free(root);
root= NULL;
}
else if(root->left == NULL)
{
struct Node* temp = root;
root = root->right;
free(temp);
temp = NULL;
}
else if(root->right==NULL)
{
struct Node* temp1 = root;
root = root->left;
free(temp1);
temp1 = NULL;
}
else
{
struct Node* temp2 = Findmin(root->right);
root->data = temp2->data;
root->right = Delete(root->right, temp2->data);
}
}
return root;
}
main()
{
root = NULL;
char ch, L, H, ch1;
int HT;
HT = Height(root);
printf("Before adding data the height of the tree is: %d
", HT);
root = Insert(root, 'L');
root = Insert(root, 'F');
root = Insert(root, 'P');
root = Insert(root, 'S');
root = Insert(root, 'O');
root = Insert(root, 'E');
root = Insert(root, 'B');
root = Insert(root, 'A');
root = Insert(root, 'M');
root = Insert(root, 'R');
root = Insert(root, 'Y');
root = Insert(root, 'V');
root = Insert(root, 'D');
root = Insert(root, 'H');
root = Insert(root, 'J');
root = Insert(root, 'S');
root = Insert(root, 'Q');
root = Insert(root, 'W');
L = Least(root);
H = Highest(root);
printf("The least character is: %c
", L);
printf("The highest character is: %c
", H);
HT = Height(root);
printf("After adding data the height of the tree is: %d
", HT);
printf("The level order travarsal of the tree is.
");
Level(root);
putchar(10);
printf("The Preorder travarsal of the tree is.
");
Preorder(root);
putchar(10);
printf("The Inorder travarsal of the tree is.
");
Inorder(root);
putchar(10);
printf("The postorder travarsal of the tree is.
");
Postorder(root);
putchar(10);
printf("Enter the item to be searched and deleted.
");
scanf("%c", &ch);
if(Search(root, ch)) printf("Data found.
");
else printf("Data not found.
");
printf("Enter the data to be deleted.
");
scanf(" %c", &ch1);
if(Search(root, ch1))
root = Delete(root, ch1);
else
{
printf("Data to be deleted is not found.
");
return 0;
}
putchar(10);
putchar(10);
putchar(10);
printf("After deletion of the data the new tree structure is:
,");
L = Least(root);
H = Highest(root);
printf("The least character is: %c
", L);
printf("The highest character is: %c
", H);
HT = Height(root);
printf("After adding data the height of the tree is: %d
", HT);
printf("The level order travarsal of the tree is.
");
Level(root);
putchar(10);
printf("The Preorder travarsal of the tree is.
");
Preorder(root);
putchar(10);
printf("The Inorder travarsal of the tree is.
");
Inorder(root);
putchar(10);
printf("The postorder travarsal of the tree is.
");
Postorder(root);
putchar(10);
return 0;
}
Your lectures r awsm..bt plz increase ur speed of uploading new videos....we r eagerly waiting for more lectures in this series...plz be fast
ankit mathur - We are also trying to figure out how to speed up. :P We focus on quality and its not so easy to speed up with quality. But we will try our best and publish videos more frequently. :)
people are hungry for knowledge :p
ankit mathur I hope he will upload a spelling video too.
I cannot say enough how helpful these videos are. You are literally saving my grade, one video at a time. Thanks for being an amazing teacher, these videos are the BEST.
you could have said these videos are the BeST ;)
😂@@rayaankhan787
for (i=0 ; i < inf ; i++){
System.out.println(" Thank you ");
}
This will not compile...Rather it will give an error...
class name not declared..
no main function..
data type of "i" unknown..
"inf" is unknown..
Great explanation! Thank you.
By the way, I'd like to point out that this deletion algorithm is not suitable for balanced trees since it will not preserve the balance. This algorithm is called Hibbard deletion, and one company was sued in the past for implementing this algorithm as the deletion method in a Red/Black tree implementation.
This is only for binary search tree .. it won't work for AVL trees and Red Black trees
A Doubt again.... in case you are deleting a node with a single child, how are you establishing a link between the parent of that node to the left || right child of that node? (I mean the algorithm isn't explaining that)
Really a good explanation of BST.Worth watching to this tutorial.Neatly explained.Thank you so much.
This is amazing. Do tutorials on AVL trees, B Tress and hash tables. Please, pretty please?
@@amitdutta5610 Harsha SuryaNarayana , one of the best coder that India has ever produced.
@@adityaatri2053 the humblefool
He is not alive .
@@adityaatri2053 he is not Harsha, the video maker is Aminesh he left making a video anymore since his partner died in accident and Animesh joined Google, therefore no time.
Brother unfortunately he is no more..!!
Thanks for the video. Question on case 3, if there are two 17's on the right side, the tree would become invalid because you would have a value that is
I took the baby steps of programming (DSA) from this channel and after 7 years I am here again for my interview preparation. Only if the channel was continued we would have seen the golden content. But destiny had some other plans. :(
excellent explanation of deleting element from BST.
Thanks.
I had a hard time understanding the deletion process from BST, especially the third case, when a node we want to delete has both of its children. This video has made me understand, you explained very clearly, and I came to realize that the procedure is actually quite simple haha. Thank you very much! Your channel is my favorite when it comes to algorithm tutorials! Please keep posting more, I really enjoy them!
Same Here Right now for me.
i had a lot of trouble understanding this! thank you so much! clear as hell explanation where all other lecturers failed. clear and simple and to the point! you are awesome my friend awesome!
In other words...If the node have two child then it should be replaced by the INORDER succession after the deletion
I usually don't leave any comments, but this was very clear and helpful!! Thank you so much
best explanation on youtube in my opinion, this helped me when I took data structures and algorithms and it helped me again when I went to tutor it a year later. Well done and thank you.
and there goes one more excellent video..
A headache concept(for me), explained in the most simple way! Pure brilliance.
Thank you, I'm a Vietnamese. Somehow, I won't understand what ever my people talk about this. :")))
what if 17 have 2 children (left and right) in the 3rd case
exactly my thought.
someone please continue this series , after the death of the owner no one is there to complete this series in the way he is continuing and i do not think any other can teach coding like this.
Your explanation was so good..I understood everything..but I have a question if the node 7 had only a left child..let's say node 4 and we want to delete node 7 then what to do ??? if we make node 4 the right child of node 5 (the parent of node 7)..doesn't that violates the property of Binary search tree????please answer anyone...lots of thanks..🙏🙏
If Node 7's parent is node 5, then Node 7 can't have a childe of Node 4, because all the value on the right of node 5 should be greater than ndoe 5.
please upload the video of hashing,avl trees ,graphs.i have been watcing your series and it helps me alot in clearing the most difficulty parts.
what if 17 has 2 nodes, examplef 16 and 20 ??
Really sorry to know that co founder harsha is no more. Really appreciate whatever you guys have done for us
HERE IS THE COMPLETE CODE:
/*
Delete node in a binary search tree of integers
Node is defined as
struct Node
{
int data;
struct Node* left;
struct Node* right;
}
*/
Node* FindMax(Node*);
Node* DeleteNodeInBST(Node* root,int data)
{
if(root==NULL)
{
return root;
}
else if(data < root->data)
{
root->left = DeleteNodeInBST(root->left, data);
}
else if(data > root->data)
{
root->right = DeleteNodeInBST(root->right, data);
}
else
{
//case 1: No Child
if(root->left == NULL && root->right ==NULL)
{
delete root;
root = NULL;
}
//case 2: one child
else if(root->left == NULL)
{
struct Node* temp = root;
root = root->right;
delete temp;
}
else if(root->right==NULL)
{
struct Node * temp = root;
root=root->right;
delete temp;
}
//case 3: two children
else
{
struct Node * temp = FindMax(root->right);
root->data = temp->data;
root->right = DeleteNodeInBST(root->right, temp->data);
}
}
return root;
// Complete this function only
// Do not write main method
}
Node* FindMax(Node* root)
{
if(root == NULL)
{
return root;
}
else if(root->right ==NULL)
{
return root;
}
return FindMax(root->right);
}
Anyone here from TOP (The Odin Project)?
Me!
What if in case of a single child the child is the left node, for example thecurrent node 9 can be a left child of 7 as well. It can be something like node with value less than 5.
case 3:
//2 children
root->right=Delete(root->right,temp->data)
what we are storing in root->right??
what Delete is going to return
After every Delete call it returns NULL.
@@manikantaneerugatti5206 after every Delete call it returns root
Guys shouldn't we store the root in a temp Node? The function returns pointer to node and we lose our pointer to the root.
You are a proof that not every indian accent video is a bad video.
Hi, How are you making sure that once the node to be is deleted is deleted and the link to its parent is still maintained now between the child of the node deleted and its parent ?
More specifically,
else if(root->left == NULL) {
struct Node *temp = root;
root = root->right;
delete temp;
}
After deleting the temp, what about the link between temp's parent and current root ? I am little confused here.
Please explain if I am wrong.
Thanks,
root = root->right sets the pointer to a node we want. In the same iteration root is returned to the previous call of Delete. Here root->right = the returned root address. This will create the new link
+Sumit Vohra root = root->right; just set a variable root pointing to root->right, so it wont create any new link. Your right. I dont think the code will work.
+Sumit Vohra I dont even understand why he created temp then delete it, what's the point of creating it and not using it at all?
If anyone is still wondering about this, look at the START of the code, where the right = delete. It will all make sense then.
he is just creating temp to free the memory, if he doesn't take temp then there will no reference to that memory and then you won't be able to free it.
No te la puedo creeeeeeeeerphiteeee
Good job ! clearly explained. There is just one remark about case 3 :In your example, you assume that the minimum Y is the right child of the deleted node Z, which is not always the exact : It could be somewhere else in Z's right subtree which have no left child (of course) but has a right subtree. In this case, if you just copy the node Y into node Z, and after that delete node Y : this won't work i think, because Y's right subtree will be lost.
I think you are right. When the node to be deleted finds the minimum in the right subtree, we need to verify if the parent of the right minimum is same as the node to be deleted. If yes, we do the same as what the instructor in this video said, otherwise we need to find the parent of the right minimum and set the left reference to NULL. I wrote this in Python like this (for the case with 2 children). I know I am answering 7 years later! 🙃
found = self.get_node(val)
parent = self.get_node(val, True)
right_minimum = BST(found.right).get_minimum()
parent_right_minimum = self.get_node(right_minimum.val, need_parent=True)
found.val = right_minimum.val
if found is parent_right_minimum:
parent_right_minimum.right = None
else:
parent_right_minimum.left = None
In my case, I wrote a get_node function to find a node in the BST with the value needed. I also have an optional parameter in that method that gets me the parent of the node with the value I was looking for.
Thanks for the videos, would have been good if I discovered this videos at the beginning of my education
this method is so much better than the method suggested in my "introduction to algorithms" textbook. Much easier to understand, and the code is cleaner. Great job!
Very well explained! Thank you! I have a question. So since deleting max from right subtree and min from left subtree both make deletion work(for the case when a node with 2 children), which subtree do we choose?
best explaination I've found for this.
root=NULL will do nothing. outside the function
Thanks! Your explanation was easy to follow
i do not think there exist any channel which is comparable to "my code school" , this guy explains the code in the most easy and logical way while others do spoon feeding .
Thanks to you; now I'm more confused 😕
That minimum value in general case(in case of characters or any other data ) is inorder successor
if you want to update then root->right=function() or else just function(). Here you need to update each and every process. And get the upmost root.
after 10 years thank you sssssssooooooooo much
After looking through so many resources, I must say that your explanation is indeed the best one on this topic. Really easy to follow and understand.
Thank you !
Out of all the search results UA-cam shows me when I search a specific topic
I always look for mycodeschool Videos.
Simply outstanding!
i hate the way he talks, that sleepy raspy voice is annoying af.. also no one else explains this concept as good as him. what a situation 🥴🥴🥴 suffering while learning
I don't get it. Can anyone explain to me, please?
In the case of delete a leaf ( a node that has no children), root is a pointer to the current node that we're dealing with, right? So if we set root = NULL after delete root, it doesn't mean that root's parent->left or parent->right is set to NULL. The way I understand it, root and parent->left or parent->child are two different pointers pointing to the same node (the leaf that we want to delete). Am I right?
I think you're forgetting that after every call of the Delete function, the root is returned so therefore after root is set to null it will be returned to the call 'root->child = Delete(root->child, data);' which will be equivalent to the call 'root->child = NULL;'
in the case of 2 children at 16:15.
in case 3, 3rd line shouldn't we pass address temp instead of root->right.pls explain
The temp is just a temporary variable to copy the data. We replace the data in the node to be deleted with the minimum value and then delete that minimum node. So, we have to pass the minimum node's address but not the temporary node address.
@@frozentaco143 yes but if you see, temp is pointing to minimum node of the subtree, which is what we want to delete. If we pass root->right, the function will have to traverse the subtree again to find the node having the min value (temp->data), whereas we already have the temp pointer pointing to the min node from temp=FindMin(root->right);
@@frozentaco143 ok I understood now. This delete funtion delete(root->right, temp->data) will return the new root node of the root->right subtree too, which is getting assigned to root->right 👌 so either way, temp node is getting deleted
I was obsessed with the tutorials of nptel.But now you guys are my brand new obsession after this video.
wow :)
Really True...After a long search found this Wonderfully Explained Video link for Data Structures and Algo..Specially for interview preparation so helpful.:):)
The findMinimum of the right sub tree should have returned 13 and not 17 right.
The findMin finds the minimum of the current node's (the node from where the call is made) right sub tree. So, it is 17. Do not confuse it with the BST's root.
give this man a cookie!! 🍪
Pretty good explaination!
this code will break when an element to be delated is not present in the tree...
#include
#include
using namespace std;
struct BSTNode{
int data;
BSTNode *left;
BSTNode *right;
BSTNode(int);
};
BSTNode:: BSTNode(int val){
data=val;
}
BSTNode* insert(int data, BSTNode* root){
if(root==NULL){
BSTNode *r=new BSTNode(data);
return r;
}
if(datadata){
root->left=insert(data,root->left);
}
else{
root->right=insert(data,root->right);
}
return root;
}
void print(BSTNode *root){
if(root==NULL){
return;
}
cout
Here is my code for finding the max in the left subtree. anyone can help check if my logic is sound? My main struggle was whether to just call delete() without assigning it to root...
else{
Node* temp = findMax(root->left); //Returns ptr to max @ bottom of tree (case 0 no children)
root->data = temp->data; //Overwrites the data of the "deleted node" to the data at bottom
delete(temp,temp->data);
/* If I wrote root=delete(temp.temp->data) then root=NULL. but i need to return the address of the node that was originally intended to be deleted in order for the tree not to break */
return root; //returns address of root
}
If i simply wrote root->left = delete(root->left, temp->data) as with what the video does, doesn't it waste more time traversing down the list? it would be better to call delete but not keep it at any pointer value right?
Why is the root pointer the only one to get assigned to NULL after being deleted ? why don't we do that for temp pointer too ?
Looks like it fail if you try to delete 12 from the BST, as 12 is equal to root.data, and we don't have condition to handle when data = root.data.
Please have a look.
We have condition to check if data > root.data or data < root.data, what missing is data = root.data
I tried this on my end, below is the python version of doing the same.
# CASE 1: Delete root of the binary tree
elif (data == root.data):
temp = root
newRoot = root.left
root = root.left
# Move current root to the end of right most node of the left subtree
while(root.right != None):
root = root.right
if root.right == None:
root.right = temp.right
del temp, root
return newRoot
This series is beautifully crafted. completely flawless . i would even pay to watch your videos.
Unfortunately he is dead 😔
@@sharmanihal99 you're kidding right?
Question! When it comes to delete a node that has 2 children, after "root->data = temp->data" in the code, why I can't just "delete temp"? (instead of "root->right = Delete(root->right, temp->data)") I tried just deleting the temp and it didn't delete the node.. Thank you
Hey, I have a question, could someone please explain to me, what would happen if for example instead of using a temp variable we would assign root = root->left ?
we need temp to temporarily store the root value and then free the node in memory
Sir in the case with both the children are not NULL
struct Node * temp= FindMin(root->right);
root->data=temp->data;
root->right = delete(temp->data,temp):
Here the last line will make the right child of the node that we want to delete to NULL .Thus we loss the access to those nodes in right.
Your lectures are awesome,easy to understand and practise. Thanks for your effort.
I think in case 3 of 2 children if you pass the recursive command: Delete(temp,temp->data); the time taken for the algorithm would reduce. Am I right in believing so?
why after free(temp) you haven't write temp=NULL? ONLY THE MEMORY IS DEALLOCATED BUT WHAT HAPPENS TO THE ADDRESS OF TEMP POINTER?
hello sir, can you plz find the bug in my code... giving segmentation fault after traversal
void delete(node *p)
{
if(p->left==NULL && p->right==NULL)
{
free(p);
p=NULL;
}
else if(p->left==NULL)
{
node *q=p;
p=p->right;
free(q);
q=NULL;
}
else if(p->right==NULL)
{
node *q=p;
p=p->left;
free(q);
q=NULL;
}
else
{
node *q=max(p->left);
p->info=q->info;
delete(q);
}
}
i have made a few changes..
first of all i have defined root node globally
and p is the node to be deleted...
Man of magic. 10yrs old. Still we re watching
what a nice explanation sir
In the else if conditions of the delete function, why don't we need to allocate memory for the temp variables?? In the getNewNode function we have allocated space for the NewNode and then inserted the value into the node...but here we have directly entered the data into the temp variable (struct node* temp = root; ) without the statement [struct node* temp = (struct node*)malloc(sizeof(struct node)) ]
8:13 I would explain this before showing how to do it instead of showing how you do it and then explaining why.
Why not just replacing it with maximum of left sub tree for case 3. You know it can have at most one left child which would take its place.also the maximum of left sub tree is bigger then any node of that sub tree but always smaller than the nodes of right sub tree.
Was in right subtree in case for deletion of a node having 2 child's. How are you taking the value 17 as the minimum in the right subtree wasn't it was supposed to be the value 15 in the right subtree ??
At 8:52 you state that all the nodes in the right sub-tree are greater or equal, whereas in other videos you say that only the nodes in the LEFT subtree can be equal.
Yeah and he said the correct thing here as well. He said once the duplicate is removed,we are good. And that sentence was a school boy error. :)
You can set up a BST to be either.. either is valid
great video, your English is very clear.
Dearr seniors I noticed that some of you watch a tutorial based on the views. This is not an efficient way. Some of you might don't find what you're looking for if you target for a view
Even in 2022 this content is gold in youtube
While deleting a node with two child.... Can root node also be considered as it also have 2 childs🤔🤔🤔and if so then how to proceed and which will become root then?
Ohh you made my day sirr ❤️❤️❤️ thanks a lott
What are you trying to say at 14:16 to 14:23 .... more than 5 times but couldn't understand properly. But thanks for the videos.
My teacher told us that there are two methods of deleting node first is you delete on right and second method is you delete on left? Can anyone enlighten me? Te have test tomorrow thanks :-)
i love your accent.
Here's a shortcut:
Node to be deleted has two children:
1. Find inorder successor of the node.
2. Copy contents of the inorder successor to the node
3. Delete the inorder successor.
What if i convert the given tree into a inordered link list. Delete the given element from this link list and again convert the Inordered link list into a tree. May be not efficient but very easy one.
Great video! Would be even greater if you also give some time-complexity analysis of the operation :)
Thank you I successfully implemented this in java code.
Recursion algorithms need more time to be understood but thanks to you it took only 18:26 !!
wow good explanation but i have this Q one of my boy ask me the
*. How i can Write a program that integers 1 to 20 to a binary search tree. Assume the root node is created with value 10.
** Assume the data structure:
StructNode{
Int value;
Node*next;
};
Node *head=NULL;
Assume also that there is a value 10 in the linked list.Write a code that deletes a node with this value.Consider all the following cases:
a. The node is at the head
b. The node is at the middle
c. The node is at the end
TLDR: If you want to delete node N and it has...
(1) 0 children, trivially delete N.
(2) 1 child, delete N, then re-link N's parent to N's child.
(3) 2 children, then find the *smallest* descendant of N's *right* child, delete it, and copy its value into N.
(Or, alternative case 3: replace bold words with *largest* and *left* , respectively.)
Your videos are probably the best explanations i have ever got! Thank you so much!
why do we need to delete? Is it necessary for the program to work? can't we just do something like root=root->left... without temp pointer
if you just delete without the temp pointer how will you return the pointer to keep the binary tree intact?
and yes, you need to delete the nodes or else you will have memory leaks of nodes that have been dynamically allocated on the heap. rule: every new has to be deleted.