In this video we walk through how to perform searches in a Binary Search Tree. Starting with a perfectly balanced BST, we cover the search process step by step, including finding existing nodes like 73 and determining that numbers like 44 do not exist in the tree.
We discuss time complexity for searches in BSTs – O(log n) on average for balanced trees and O(n) in the worst case when the tree becomes skewed like a linked list due to sorted or bad data. Learn why each comparison eliminates half the remaining data and how height affects performance.
Perfect for students learning data structures and algorithms. If you’re studying BSTs, this clear explanation will help you understand searching, insertion paths, and why self-balancing trees matter.
Thanks for watching!
00:00 Introduction to BST Search
00:31 BST Not Self-Balancing
00:40 Average Case Log Time
00:53 Linear Time in Worst Case
01:13 How BST Search Works
01:18 Search Path Example
02:08 Searching for Existing Node
02:35 Searching for Non-Existent Node
03:19 Tree Size and Height
03:30 Time Complexity O(h)
05:40 Bad Data Example
08:23 Skewed Tree Like Linked List
09:53 Linear Time in Worst Case
11:58 Why Log Time
12:36 Halving the Search Space
14:14 O(log n) Summary
14:28 Conclusion
=-=-=-=-=-=-=-=-=
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
hey there let’s perform searches in a binary search tree
okay if you watch my previous videos you know how to define a binary search tree by now
you know some terminology you know how to construct a tree and so now let’s just take
a tree that’s already been constructed and let’s search through it first thing i want to say is
first thing I want to say is this is a binary search tree this is not a self
balancing tree so in the future this tree could get lopsided and messed up
depending on what kind of data we add we can always expect that binary search
trees have a search time or an insert time or removal time of log log base 2
of n on average assuming that the data is random or in the worst possible case
scenario linear time so these could get slower right now you can see this tree
Right now you can see this tree is perfectly balanced.
So if we say that our tree is currently perfectly balanced and it’s always going to be perfectly balanced,
which is a fantasy, but let’s just say that it is,
then we could just say it’s a log tree.
It’s going to take log time to search through.
So how do we perform searches?
Again, if you saw my previous videos, you should know that it’s really easy to find out where a node belongs.
Like for example, if I was going to add the number 14,
I would first look at the root node and I’d say, okay, the root node is occupied.
and I’d say, okay, the root node is occupied.
And so where would 14 belong?
Well, it would belong on the left of 37
because it’s less than 37.
It would belong on the left of 16
because it’s less than 16.
It would belong on the right of 9
because it’s greater than 9.
It would belong on the right of 11
because it’s greater than 11.
And so the 14 node that we just wanted to add,
is that what I just said, 14?
Would end up going there.
So when you’re searching through a binary search tree,
you really just have to go find
have to go find where the node would belong as if you’re performing insert or you could think of it
the other way around like insert is really thinking of a search first but basically we’re just going
to start by saying you know pick a number and we’ll see if it exists so uh let’s pick the number
67 or actually let’s pick the number 73 just to see if it exists in the tree so 73 i’m going to
do like you know seven three with like a question mark we check the root node 73 belongs on the
side we look at the 59 it belongs on the right side and we found our 73 so 73 exists in the tree
and it only took us three examinations only three examinations let’s look for a number that doesn’t
actually exist in the tree so maybe oh my thing is freezing what’s going on okay so maybe uh let’s
The 37 here, 44 belongs on the right of 37.
We look at the 59, it belongs on the left.
We look at the 48, it belongs on the left.
We look at the 43, it belongs on the right.
The 44 would have been there, but it’s not because that right child pointer off the 43
is null.
So we only had to really examine one, two, three, four nodes in order to determine that
our number 44 didn’t exist in the tree.
Notice how we’re not doing a lot of examinations compared to the total size of the tree.
compared to the total size of the tree.
So let me just write this up here.
How many nodes do we have?
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
We got 15 nodes up here.
Someone say N is equal to 15.
And what’s the height of the tree?
Remember, the height of the tree is the number of nodes you must touch
as you make your way down towards the deepest node.
Or if you’ve already found the deepest node,
you take its depth and you just add 1, assuming that depths start at 0.
start at zero. So I’ll just say that the depth of the root node is zero and the 59 and the 16 are
one. And then that third row is two. And that last row is three. And then I just add one to the
deepest node that I can find, which is just going to have a depth of three. All of these on the
bottom row have a depth of three. So the height of this tree is actually four, because we would
so like 37 59 48 43 that’s four touches um or the or the depth of the deepest node plus one okay um
all trees all binary search trees whether they’re actually avl trees or regular binary search trees
or whether they’re balanced or imbalanced they’re always going to have a time complexity to search
through of o of h meaning in the worst case scenario you’ll have to touch h number of nodes
order to find a node by search query or to add a new node or even to delete a new node.
So how does that compare to this tree in reality?
Let me just open up a little calculator real fast.
I just want to show you.
So if we do log base two, because we have a binary search tree, not a trinary search
nodes 15 it tells us that it should take us no more than four examinations to find the node that
we’re looking for if the tree was perfectly balanced and if you if you if you notice that’s
exactly what the height is telling us here if the tree was more imbalanced the height would get
really bad compared to the number of nodes and it would no longer be considered a log tree it would
just be you know somewhere in between linear time and log time um let’s see what else can i show you
let’s do well we did that computation let’s do a search through the tree that
through a tree that’s actually really really bad let’s pretend that we have a
bunch of nodes here and you know I’ve got an old story that I love to tell
about this when like when my grandma was alive she was kind of bitter towards the
end you know I loved her but she used to call the cops on her neighbors for
gossip and at some point in time she got into a feud with her neighbor who was
with her neighbor who was also a bitter old lady.
You know, towards the end, it kind of happens sometimes.
It sucks, but it happened.
And I guess the neighbor didn’t like my grandma’s tree
that she had in her backyard.
So they fought over it, they argued over it,
and then one day my grandma said
she was looking out the backyard window
to yell at ducks who were jumping into her pool
because she just hated when the ducks went into her pool.
She was waiting for them to show up.
She wasn’t even looking at ducks.
even looking at ducks she was just waiting and she saw the other little old lady reach her arm over
the fence and spray my grandma’s tree with some sort of poison then my grandma’s tree died and uh
i guess you know my grandma never never got over it i always thought it was like a funny story it
was a little sad but um she poisoned my grandma’s tree so we can kind of do the same thing with the
binary search tree we can give bad data let me show you what happens here if i use this data set
search tree. So we’re going to add this node right here. It’s going to be the 14.
And then when we add the 19 node, I’m just going to duplicate it. The 19 is supposed to be on the
right side of 14 because it’s greater than 14. So I’m just going to like, you know, draw a 19 right
here and a little connecting line. Okay. Then when we add the 24, I’m going to duplicate this node
the 24 go belongs on the right side of the 14 and also belongs on the right side of the 19
because it’s greater than 19 so again we have a node that shows up on the right side let me
remember to actually fix the 19 so it looks like 24. then when we add the uh 29 it’s gonna end up
being the same thing right the 29 is gonna end up showing on the right the right the right it’s
If we have bad data, we can end up with a tree that kind of looks like a straight line.
And if you are watching this video from the future,
after I’ve posted all of my data structures videos that I have,
you might notice that this looks like another data structure.
If you’re watching this right away, I haven’t posted those videos just yet.
But just tilt your head to the right a little bit
and tell me if that looks like something that you recognize.
It looks like a linked list.
looks like a linked list just like a straight line or even i guess you could kind of say maybe an array
um just like a straight line of data there’s no uh you know there’s no splitting of the data
so we have the 29 and then the 35 and then uh maybe i’ll just do one more node only and i’ll
get rid of that 54 because that’s too many nodes so what happens is if you have you know bad data
tree doesn’t actually search or add insert or remove or anything like that in log time anymore
instead it operates in linear time just like a linked list would meaning we would have to scan
through every single node in the entire tree to be sure that some value did not exist well
not exactly but in the worst case scenario we’d have to scan through the whole entire tree
for example let’s just look at the the number of nodes real fast we’ll say the
number of nodes here is one two three four oh I put two 24s in there oh dearie
let me get that says 14 19 24 29 and then I guess I got to make that a 35 oh
okay and then there’s a 49 I guess I did add every single node okay so we added
so there’s like seven uh items in the tree so i’m going to say n is equal to seven the height also
is seven though so the height is seven notice how if we say that it’s always true that a binary
search tree has a time complexity in the worst case of o of h meaning you’d have to go down
in the worst case the number of levels that is equal to the whole entire height of the entire
tree that’s also the number of nodes in the tree which means uh if i wanted to add let’s say the
I don’t know, if you wanted to add the number 60,
60 would end up going down here.
And in order to find where 60 would go,
we’d have to look at the 14, that’s 1, 19, 24.
We’d have to look at all these nodes.
That is seven nodes.
We’d have to examine seven nodes
just to figure out where the 60 would go.
Or if we were searching for 60,
then we’d have to go down that far
to find out that 60 didn’t exist.
So this is nowhere near a log tree.
This is a linear tree, a linear time tree.
year time tree and just to drive the point further if we did log base two of the number of nodes in
this case seven notice how it’s telling us that we should if it was a log tree if it was perfectly
balanced or a self-balancing tree we should have to touch no more than three nodes in order to find
what we’re looking for to search through the tree or to insert a new node or even to delete a node
but that’s not the case here because the tree is really really slow compared to a perfectly balanced
slow compared to a perfectly balanced tree.
So we call this a linear tree.
It sucks.
You want to try to avoid that.
You don’t want your data to be poisoned.
On average, your trees won’t really look like this if you just have totally
random data, but if you think there’s a chance that your data might be skewed
in some way, it’s probably a good idea to upgrade to a self-balancing tree,
which we’re going to talk about later.
Okay.
What else can I tell you real fast?
So we talked about searching.
why are these trees considered log time? I mean, they’re really, really fast, but why?
Let’s just duplicate this slide here and I’ll move it down one level. I just want to kind of
show you why this ends up being a log time tree. Okay. So why, why is this a log time tree?
Suppose for the sake of argument, we’re searching for the number 52. So if we’re searching for the
node the root node and decide where would the 52 belong let me actually write that down so i don’t
forget 52 question mark where would the 52 belong it would belong on the right side of the 37 because
it’s greater than 37 right which means it’s actually impossible that the 52 would be in any
of these other nodes on the left side there’s no need to check them we’re not going to scan the
whole tree we’re just going to go left or right and ignore the whole other side of the tree
we just did is with one examination we eliminated half of the remaining data set or i guess of the
initial data set if we’re looking at the root node so then the next thing that we do is we just kind
of say okay it belongs on the right side so we look at the 59 node and we do the same thing we
say where would 52 be would it be on the left side or the right side of the 59 node it would be on
the left side which means we’re going to eliminate from consideration the entire right subtree of the
So again, we’re eliminating half of the remaining data set.
Then we kind of go down here and we look at the 48.
We do the same thing.
52 belongs on the right side.
So we eliminate half of the remaining data set, you know, and then eventually we do find
the 52 and then that’s it.
So if we’re eliminating half of the data set with every single, just one examination at
a time, that’s why it ends up being log base two.
getting twice as close to your destination at every step you took if you’re like in a car like
running maybe you’re on the moon or something then it would be a log time you know uh progress
towards your goal or eliminating half of the data set at every single step sometimes people see
for loops on exams and stuff when we talk about this um like for i equals zero uh i is less than
it would be like i times equals two.
So i’s jumping twice as far each time.
That’s the sort of thing that makes it log.
So I’m just going to write down log here real fast
to drive the point home a little bit more.
O of log base two of n.
Yeah, so I guess that’s all I wanted to tell you in this video.
Hopefully you feel like an expert in searching now.
If you want to see more searching videos,
leave a comment or something like that.
leave a comment or something like that. But yeah, thank you for watching. And I hope you
learned a little bit of stuff and had a little bit of fun. I’ll see you in the next video.
I’m going to go find a blueberry muffin.
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,
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 or just i’ll be able to keep making videos in general so please do do me a kindness
and uh and subscribe you know sometimes i’m sleeping in the middle of the night and i just
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
And I just subscribe and then I’ll just wake up. I promise that’s what will happen
Also, if 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
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 see please leave a comment or if you 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. I’m like this
It would really it really mean the world to me. I would really appreciate it. So
So again, thank you so much for watching this video and enjoy the cool music as I fade into the darkness, which is coming for us all.
Thank you.
