Hello there. In this video we break down exactly how to delete nodes from a binary search tree. We cover all three cases step by step: deleting a leaf node with zero children, deleting a node with one child by promoting it, and the trickiest case – deleting a node with two children using the in-order successor method.
You’ll see clear diagram walkthroughs, pointer manipulation explanations, and time complexity discussion for each type of removal. Perfect for computer science students, coding interview prep, or anyone strengthening their data structures knowledge.
We search for the node, identify its children, and handle the reconnection properly to maintain the BST properties. Includes examples for each scenario and tips for implementing in code.
If you’re learning BST insert, search, and now removal, this completes the core operations.
00:00 Introduction to BST Deletions
00:10 BST Review and Setup
00:46 Three Types of Deletions
00:56 Deleting a Leaf Node (Zero Children)
03:21 Pointer Manipulation for Leaf Deletion
05:25 Deleting a Node with One Child
07:17 Pointer Updates for One Child Deletion
10:09 Deleting a Node with Two Children
12:08 In-Order Traversal and Successor Concept
13:18 Finding In-Order Successor
14:20 Copying Successor Value and Recursive Delete
18:28 Deleting the Root Node Example
22:56 Additional One Child Successor Example
25:12 Time Complexity Summary
26:08 Closing and Outro
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main “pinned” video of this channel for offers and extras
Hello there. Let’s talk about deletions in a binary search tree.
Okay, so hopefully at this point you already understand binary search trees
in all other aspects than just deleting. If you don’t, see my other videos. In my other videos,
we talk about how to identify a binary search tree, all the rules that define it,
search tree with the insert or add operation.
We talk about searching through a binary search tree and time complexities
and even drawing the diagram in a really nice and pretty way so that your trees
are easier to debug.
So for now, I’m just going to say it’s time to learn how to delete notes from
a binary search tree.
So there are three types of deletions.
Actually, let me just kind of like, for example,
suppose you want to delete to delete the number 48 from the tree.
48 from the tree. Okay. Well, first you’d have to go search for 48. So already, you know,
this is going to be an O of H operation or log time. If the tree was perfectly balanced
or linear, if the tree was really poorly balanced. So we’re going to search for,
what did I just say? 48. I should write it down. Let’s say we’re going to search for 48.
We have to go search for it first. So that’s going to be O of H. Once we find it, we then
How many children does it have?
Is it a leaf with zero children?
Is it a node with one child?
Or is it a node with two children?
Each type of node is deleted in a different way.
So let’s see, the first type we would delete
is a node with zero children,
also known as a leaf, also known as a, sorry, external node.
The second type of deletion is a node with one child.
with one child and the third type is going to be the hardest type we’ll do that at the end of the
video it’s going to be a node with two children uh numbers two and three are going to be internal
nodes but i hope you already know that because you watch the videos anyway so let’s start off
with the easiest possible node to delete first just a regular leaf so i’m going to delete this
stuff real quick um and then just kind of like erase that and down and down okay so let’s identify
so let’s identify a leaf well it could be anything that just doesn’t have any
children of its own let’s do let’s do the number 11 just to make things a
little bit easier so let’s delete the number 11 I’ll put 11 here we first
search for 11 so we look at the root node 11 belongs on the left we look down
here 11 belongs on the left we look down here 11 belongs on the right we find 11
you know if we reach the end of the tree and we couldn’t find it then it’s like I
don’t know maybe throw an exception at the user hey you tried to delete
tried to delete something that wasn’t there but the 11 is there and now we have to figure out how
to actually delete it so let me draw a couple of larger representations of these nodes real fast
i’m just going to draw like a big old circle here and maybe duplicate it and we’ll just pretend that
that’s the 9 and the 11 so i’ll put like a tiny little 9 there because i don’t want to change the
And when we draw our diagrams, we usually just kind of do one line.
But you should know that if you’re doing this in code,
actually what’s happening is the nine node,
it’s got a right child pointer that points down to the 11 node.
And then the 11 node has a, let me just redo this real fast to make it prettier.
And then the 11 node has a parent pointer that points up to the nine.
This is probably going to be true for almost every language,
at least that I can think of that you would code a tree in.
a tree in. And then of course the nine would have a parent pointer to you know the 16 but we won’t
consider that. So what are you really going to do? Well first you have to look at the 11 node and
travel up to its parent and let the parent know that it no longer has a right child. So long story
short we’re going to null the right child pointer. We’re going to say disconnect that right child by
setting it to null. Maybe I’ll just put like a little null symbol here. Then we don’t necessarily
null the pointer on the 11 node because we can just delete the 11 node if we’re
using dynamic memory if we’re using a smart pointer it should go away already
at this point because it has no one else pointing to it but long story short
once we kill the 11 node we also end up killing its pointer so we don’t really
need to tell its pointer to point to null it’s just going to end up going away
it’s not going to be a memory leak because it was only pointing to the 9
and the 9 is not going to leak memory because the 9 is still going to be inside
going to be inside of the tree so uh the time complexity once we find the the leaf the node
with zero children is just going to be constant time we’re just going to manipulate a couple
pointers maybe call delete on that node so it’s really all about log time to go find the node if
it was perfectly balanced or just o of h to find it and then plus constant is going to get cancelled
out so it’s like an o of h operation or log time if the tree is perfect so let me just uh
cross it out to let you know that this is what it’s going to be like.
We’re going to say the 11 is just gone,
and so is the pointer that the 9 has pointing down to the 11.
That’s how you delete a node with zero children.
So deleted a leaf.
All right, now the next thing, which is slightly harder, but not too hard,
is deleting a node that has one child.
Long story short for this, we’re pretty much just going to…
oh I forgot to full screen the annotator let me do that to get myself a little more room
we’re really just going to promote its one child to wherever that node was so let me erase this
real fast and we’ll say that let’s first let’s find a node with only one child it’s not the 35
it’s the 32 node okay I guess that’s why I drew that so let’s kill the number 32
You know, if there was just like one child, like let’s say the 23 was the only node that existed
and there were no nodes underneath the 23, then this would really be the same operation. We would
literally just promote the 23 up to where the 32 was. But I wanted to do this example because it’s
a little bit more difficult. So we want to kill the 32. What we’re going to do is first search
for it. So this is already going to be an O of H operation or a log time if the tree is perfectly
We do, we go down here, we go down there.
You know, where is the 32?
We’re just searching for it.
So we had to spend the time to search for the node.
We then look at the node.
Okay, we found the 32.
We identify how many children it has.
We see that this is a node with only one child.
And that means the one child, which in this case is 23, just needs to be promoted up to where the 32 is.
just you know remove the 32 from the diagram maybe get rid of get get rid of one of these uh
connecting lines and then just move the 23 up a level and that’s pretty much it if you’re thinking
about this in terms of code uh you you want to have let’s see let me duplicate this again in a
different way if you’re thinking about code what you want to do is have the 32 which is the node
you’re going to delete go to its child so determine if it’s the left child or the right
or the right child that exists once you find that child you tell it that its new parent is the
parent of the node you’re trying to delete so that means the parent of the 23 is no longer 32 the
parent of the 23 is actually 35 you know it’s its original grandparent or the the parent of the node
you’re trying to delete after you do that you tell the grandparent that it’s no longer pointing down
to the node you’re trying to delete but instead to its grandchild so again we’re just going to
So again, we’re just going to manipulate some pointers here.
We’re going to say, yep, your left child is now the 23 and not the 32.
Notice how we’re kind of, you know, drawing arrows around the original node.
We’re sort of cutting it out of the situation, just like in a linked list where you remove one node.
And this is going to be a constant time operation, at least after we search and find the 32 node.
Finally, of course, you want to like delete the 32.
you have in your tree you would call delete on it depending on your language and then uh if it was
a smart pointer uh as soon as no other nodes are pointing to the 32 it’s just going to go away so
you don’t really have to worry about it but yeah long story short uh notice how the 23 is actually
the new left child of the 35 so that’s why i say that the the uh the one child that was on the 32
is going to get promoted uh to wherever the 32 was wherever the node you wanted to delete was
this will be the same whether or not whether it’s the left child or the right child in terms of what
is the one child that the node had and also you know how do you decide how to tell the the
grandparent is its left child pointer going to be changing or is its right child pointer going to be
changing well you know when you originally looked at that 32 and you’re about to delete it you could
tell that it had that it had one child based on its left pointer and right pointer one of them
pointer one of them was null and one of them was not so whichever one of them was null that tells
you the direction that the grandparent should be pointing so in this case the 32 had a left child
pointer that was not null and a right child pointer that was null because there was no right child
so that’s why we told the grandparent that its left child pointer is now the 23.
and that’s it for deleting a node that has one child okay so uh i’m going to go ahead and delete
one more time and we’re going to do the deletion of a node let me let me write down you know deleted
a node one child yay we did it you guys um okay i’m gonna put that there too just for my notes
so this is going to be the hardest uh part we’re going to try to delete a node that has two
children maybe i’m first going to delete the uh the 35 nodes since that’s kind of where we’re
node since that’s kind of where we’re hanging out lately and then we’ll delete the hardest node of
all the 41 nodes so the first thing we need to know before we can get ready for deletion is
the in order traversal sequence of the data in this tree if you’re watching this video as soon
as i published it then i i don’t have videos up yet on traversal i’m going to upload those soon
then you can just check out one of my traversal videos.
But long story short,
in order traversal just means produce a sorted list,
an ascending list or a non-decreasing list
based off the data that’s inside of the tree.
So, you know, if I put this down here,
I can just say, you know, looking visually
from left to right, this is why I draw my trees in this way.
I see a six and then a nine and then an 11
and then a 16 and then a 19 and then a 23
and then a 29, no, no, no, a 26, and then a 29, and then a 32, 35, 38, 41, 43, 48, 52, 59, 67,
73, and 79. Let me just double check that I’ve done this correctly. The numbers seem to be
to be increasing or at least not decreasing.
Let me just double check.
Okay, how many do I have?
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
I already got lost.
I think it’s 19.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
Okay, did it right.
list, an ascending list of the original data that was inside of the tree. And now we need to look
at a concept called in order successor. Successor comes after, predecessor comes before. Think of
like a king and a prince, right? The prince is the successor to the king. Eventually one day when
the king grows very old and becomes grandpa king and the prince grows up and becomes the regular
king, then you would look at the prince king and you would say, who was your predecessor? Well,
grandpa king right so whoever comes before his predecessor whoever comes after is the successor
so we want the in order successor of the node that we wish to delete so I can’t remember what
I said originally but let’s just say we’re going to delete the 35 node I should have written it
down let’s delete the 35 first we have to find the 35 itself to make sure it exists in the tree
so I’m going to look at the 41 I’m going to go left to the 16 I’m going to go right to the 35
We found it in O time in the worst case.
So this is obviously not going to be the fastest operation, but you know, all the ops are kind
of the same speed in a perfectly balanced binary search tree, not empirically, but in
terms of time complexity.
So we found the 35, we identified that it has two children.
So then what we have to do is find the in order successor.
What is the in order successor of the 35 node?
list 35 here and it appears to be 38 and that actually makes sense because since the data in
the tree is going to look sorted if you sweep your eyes from left to right assuming you drew
the diagram well you’re really just looking for the the node that is as close as possible
to the node you wish to delete but happens to be to the right of it there are some tutorials out
there that use the in order predecessor so that would mean the 32 would be the one you select
I like to do successor.
So first we find the 35,
then we find it’s in order successor.
We’ll do another delete maybe next of the 16 node
because that’ll be a little more difficult.
Once we find the in order successor,
we’re actually just gonna copy the data up into the tree.
So I’m gonna, sorry, up into the node we want to delete.
So that means I’m gonna take this 35
and it no longer has 35 as its value.
as its value. Instead, we’re going to steal the value of its in order successor. So 35, sorry,
38 up here. So now we have two 38s in the tree. That’s bad. We need to recursively delete the 38
node. It’s not really a recursive delete. It’s more like you’re inside the remove function or
the delete function or whatever you chose to call it. It’s usually remove. And after you’ve copied
of the in order successor to the node you actually wanted to delete then you call delete or remove
again on the the in order successor you probably want to use a pointer to that node or have some
sort of a way to reference that node without telling the tree to start deleting from the top
again because if we say if we just call tree.remove with the number 38 it’s going to actually find the
38 on top and that’s going to be no good because then if you’ve written your code correctly
uh at least after that point then it’s going to find the 38 and copy its value up
and then it’s going to happen all over again we’re going to just be stuck in an infinite loop
um so instead you want to have like a pointer to this node or a reference to this node
and then call a removal function or a delete function that can receive just like you know
a reference or pointer directly to that node and then if you notice the number 38 node
So there’s actually a guarantee that when you find the in-order successor, it will only have zero or one children.
It’s absolutely impossible, unless your tree is super messed up in some way, that the node would have two children.
Because if it did, then you have not gone far enough to the left towards the node you’re trying to delete.
Remember we said we need to find the node that is as close as possible to the node that we want to delete, but just like on the right side.
the 38 had a left child then we would actually want to follow the left child we wouldn’t stop at
the 38 node so it’s impossible for the node to have two children which means it’s going to end
up being an easy deletion so the first thing we do is we’re we’re saying let’s delete a node with
two children that’s the 35 we find it’s in order successor we copy its value up and then we call
delete again or remove again on this in order successor which is guaranteed to just be an easy
leaf removal or a node with one child removal where we just like you know promote its child up
and that’s it so let me uh let me duplicate this real fast and uh let me say also that everything
we just did was basically all it’s just going to be o of h because it’s going to be o of h to go
find the node in the worst case and then o of h to find its in order successor uh some fraction of
each you know o of h fraction o of h fraction but when you just combine them it’s just going to be
It’s just going to be O or log time if it’s a perfectly balanced tree.
And then once we find the in order successor and the node we want it to delete, it’s just
a matter of like just copying data and maybe doing the second delete.
So, you know, the second delete itself would just be like another O or log time.
So you probably know at this point that if you have two times log of N, it’s just going
to cancel out to log of N if we’re talking about big O time complexity.
time complexity. Anyway, so I’m going to duplicate this one more time and then revert everything
to scratch to scratch here or to the very beginning again. So we can delete something
that’s a little bit more difficult. Whoops, that’s bad. Can I get this? Nope. Can I get
that? Yes. Okay. So let’s delete that 16 node. So we can look at how you might find the in
order successor in a program because you don’t want to like traverse the whole entire tree and
produce a giant list and then scan the list and then like find the successor and then once you
know the number go search for the for the node that’s like going to be way too slow the tree
should be way faster than that so instead this is kind of how you do it let’s search for the 16 first
so we do like 41 16 belongs on the left side we found the 16 now we have to find the 16s in order
successor the one that comes after you can tell just by eyeballing it that it’s going to be the
eyeballing it that it’s going to be the number 19, right? But how do we find that number in the code
to make it a little bit faster? So again, 16 and 19, they’re just paired up right there.
Well, first you just take a hop to the right. So you look at the right child, if it exists.
If it doesn’t, then you have not tried to delete a node with two children. It was definitely a
node with the one child at most. So we take a hop to the right to find its right child.
as far down as you can possibly go until you reach a dead end.
So that means I’m taking a hop to the right and then I’m just going to go.
Maybe I’ll do like another color here.
I’ll go left child pointer, left child pointer, left child pointer,
as far down as I can possibly go. And that is the successor.
Notice how that’s the 19. Again,
if the 19 had a child on its left side,
we would have to follow it down further,
which means it’s guaranteed that you will stop at a node that has no left child.
no left child if it had a right child same situation it’s still going to be the in order
successor that just but that just means when we call a remove a second time on that node it’s
going to be a leaf that gets removed and not a node with one child so it’s just pretty easy let
me uh let me say that now that we’ve found the in order successor we’re just going to copy the value
so i’m going to do maybe i’ll put this in orange so this 16 is no longer in that particular node
no longer in that particular node we’re not even deleting that node we’re just stealing a value
from a different node we’re going to steal the 19 value from the node which is the in order successor
and now that we’ve done that we’ll use our reference to the 19 node to call remove on it
specifically so when we call remove or delete it’s basically going to say all right what sort
of node is this um it’s not even going to have to search for the node because you gave a point
you gave a point to the node or a reference to the node it’s going to go oh this is a leaf node
that’s easy i just tell the 23 that it has no left child anymore and then i just actually
deallocate the 19 node or if it’s a smart pointer let it die on its own anyway let’s do something a
little bit more difficult now so i’m going to duplicate this and try to revert all this stuff
Okay, okay.
Let’s delete the root node, the hardest node of all, the 41.
Okay, so if we want to delete the 41 node, I’m just going to put 41 here so I don’t forget.
First, we search for 41.
In the worst case, you know, it would have been O of H, but we were lucky.
We just found it right away.
Now we have to find the in-order successor for the 41.
So again, take a hop to the right and then follow left child pointers as far down as you can possibly go.
go so we’ll look at the 48 here and then we’ll look at the 43 now we’ve hit a
dead end and we know that the in-order successor for the 41 is 43 and that
makes sense because they’re paired up here in this sorted list at the bottom
so then the next thing that we do is we just copy the data you know we steal the
data from the 43 so I’m gonna cross out this 41 here and it’s gonna end up
and then we call delete a second time or remove a second time on the actual 43 which is another
easy removal because it could not possibly have two children it’s only going to have zero or one
children and well that’s pretty much it it’s just going to be just so fast and easy so that means
the 43 is gone when we’re finished here if you look at all the slides in this video you’ll notice
notice that the data is still ordered correctly so we do have a valid binary search tree even after
we kind of do this weird data stealing let me see if i can find something that would have had one
child so i want to look through the whole tree and see if i can find a node that has one child
that would make a good in order successor and if i can’t find one i’m just going to manufacture
one real fast let’s see um who has a right child only no one has a right child only that sucks
child only that sucks all right uh let’s say we want to delete the root node again
and i think last time we just said it was the 43 how about we uh that’s boring let’s delete the 59
okay so i’m going to uh write 59 up here so i don’t forget and then we’re going to add another
node real fast so that the 50 uh sorry the 67 has a right child why am i doing this because the 67
order successor of the 59 node. So I’m just going to draw like another line real fast like that.
And I’m going to update some number. Let me just say 70 is going to be the number in that node,
which is double check that it’s increasing 59, 67, 70. Okay. So we want to delete 79,
sorry, 59. The first thing we do is we go find the 59. So I’m going to
take off my line tool. Okay. So we’re going to go to the root 59 belongs on the right side.
59 belongs on the right side so we find the 59 there it is now we’re looking for the in-order
successor we go to the right side and then we follow all left child pointers until we hit a
dead end left child pointer dead end already because i mean there is a right child but we’re
supposed to be going down left child pointers there is no left child pointer so we’ve hit a
dead end so that means the 67 is the in-order successor of the 59 which means we’re going to
67 data and put it where the 59 data was. So again, we’re not really deleting the node that
had two children. We’re going to eventually delete the node that had one child, the successor.
But 67 is the number that’s going to be there. And then we call delete on this 67. And what’s
going to end up happening is our removal function identifies that that 67 had one child. And so what
one child which is the 70 node just one level higher where the 67 was so that means the uh
the 67 is just gone we do actually delete that and then the 70 node is going to be the new
left child of the 73 node notice how the data still makes sense okay i think that’s all i’ve
log time operation just one more time log time if the tree is perfectly balanced it’s a little bit
closer to linear time as the tree becomes more imbalanced if this was a self-balancing tree then
you know this would be like log time in terms of worst case scenario in general we’ll say that this
is still on average if we had just totally random data and totally random deletions on average this
would be you know a log time operation even if we do log down to find the node and then another
uh down to find the node and then another log to find the successor that’s still not going to be
you know worse than log or o of h in general okay that’s all i’ve got for you thank you so
much for watching this video i hope you learned a little bit of stuff and i hope you had a little
bit of fun i need to see if someone is selling pi at this hour going on a searching thing
Hey everybody!
Thanks for watching this video again from the bottom of my heart.
I really appreciate it.
I do hope you did learn something and have some fun.
If you could do me a please, a small little favor,
could you please subscribe and follow this channel or these videos
or whatever it is you do on the current social media website
that you’re looking at right now.
It would really mean the world to me and it’ll help make more videos
and grow this community.
So we’ll be able to do more videos, longer videos, better videos,
videos or just I’ll be able to keep making videos in general so please do do
me a kindness and and subscribe you know sometimes I’m sleeping in the middle of
the night and I just wake up because I know somebody subscribed or followed it
just wakes me up and I get filled with joy that’s exactly what happens every
single time so you could do it as a nice favor to me or you could you control me
if you want to just wake me up in the middle of night just subscribe and then
I’ll just wake up I promise that’s what will happen also if you look at the
you look at the middle of the screen right now you should see a QR code which you can scan
in order to go to the website which I think is also named somewhere at the bottom of this video
and it’ll take you to my main website where you can just kind of like see all the videos I published
and the services and tutorials and things that I offer and all that good stuff and
if you have a suggestion for clarifications or errata or just future videos that you want to
just want to say hey what’s up what’s going on you know just send me a comment whatever i also
wake up for those in the middle of the night i get i wake up in a cold sweat and i’m like
it would really it really mean the world to me i would really appreciate it so
again thank you so much for watching this video and um enjoy the cool music
as as i fade into the darkness which is coming for us all
Thank you.
Hello there.
Let’s talk about.
