How to Search in a Binary Search Tree (BST) - Step by Step Explanation with Examples - video Dailymotion

Neural Lantern

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  binary search tree, BST search, binary search tree tutorial, data structures, algorithms, BST explained, search in BST, binary tree search, tree traversal, log n time, data structures and algorithms, computer science, programming tutorial  =-=-=-=-=-=-=-=-=  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

Transcript

00:02hey there let's perform searches in a binary search tree

00:15okay if you watch my previous videos you know how to define a binary search tree by now

00:19you know some terminology you know how to construct a tree and so now let's just take

00:24a tree that's already been constructed and let's search through it first thing i want to say is

00:29this is a binary search tree this is not a self-balancing tree so in the future this tree

00:34could get lopsided and messed up depending on what kind of data we add we can always expect that

00:40binary search trees have a search time or an insert time or removal time of log log base 2 of

00:47n on

00:48average assuming that the data is random or in the worst possible case scenario linear time so these

00:55could get slower right now you can see this tree is perfectly balanced so if we say that our tree

01:00is currently perfectly balanced and it's always going to be perfectly balanced which is which is

01:04a fantasy but let's just say that it is then we can just say it's a log tree it's going

01:09to take

01:09log time to search through so how do we perform searches again if you saw my previous videos you

01:15should know that it's really easy to find out where a node belongs like for example if i was going

01:19to add

01:19the number 14 i would first you know look at the root node and i'd say okay the root node

01:25is occupied

01:26and so where would 14 belong well it would belong on the left of 37 because it's less than 37

01:32it would belong on the left of 16 because it's less than 16 it would belong on the right of

01:369 because

01:37it's greater than 9 it would belong on the right of 11 because it's greater than 11 and so the

01:4214 node

01:42that we just wanted to add is that what i just said 14 would end up going there so when

01:49you're

01:50searching through a binary search tree you really just have to go find where the node would belong

01:54as if you're performing insert or you could think of it the other way around like insert is really

01:59thinking of a search first but basically we're just going to start by saying you know pick a number

02:04and we'll see if it exists so uh let's pick the number 67 or actually let's pick the number 73

02:10just to

02:11see if it exists in the tree so 73 i'm going to do like you know 73 with like a

02:16question mark

02:17we check the root node 73 belongs on the right side uh we look at the 59 it belongs on

02:23the right

02:23side and we found our 73 so 73 exists in the tree and it only took us three examinations

02:30only three examinations um let's look for a number that doesn't actually exist in the tree

02:38so maybe oh my thing is freezing what's going on okay so maybe uh let's look for the number 44

02:46so if

02:46we look at uh 37 here 44 belongs on the right of 37 we look at the 59 it belongs

02:53on the left we look

02:54at the 48 it belongs on the left we look at the 43 it belongs on the right the 44

02:59would have been there

03:01but it's not because that right child pointer off the 43 is null so we only had to really examine

03:07one two three four nodes in order to determine that our number 44 didn't exist in the tree

03:13notice how we're not doing a lot of examinations compared to the total size of the tree so let

03:18me just write this up here how many nodes do we have one two three four five six seven eight

03:24nine

03:2410 11 12 13 14 15 we got 15 nodes up here someone say n is equal to 15 and

03:31what's the height of the

03:32tree remember the height of the tree is the number of nodes you must touch as you make your way

03:37down

03:37towards the deepest node or if you've already found the deepest node you take its depth and you just add

03:42one assuming that depths start at zero so i'll just say that the depth of the root node is zero

03:48and

03:48the 59 and the 16 are one and then that third row is two and that last row is three

03:54and then i just

03:55add one to the deepest node that i can find which is just going to have a depth of three

03:58all of these

03:59on the bottom row have a depth of three so the height of this tree is actually um four because

04:09we would

04:09have to touch four nodes along the way to the deepest node so like 37 59 48 43 that's four

04:15touches

04:16um or the or the depth of the deepest node plus one okay um all trees all binary search trees

04:23whether

04:24they're actually avl trees or regular binary search trees or whether they're balanced or imbalanced

04:29they're always going to have a time complexity to search through of o of h meaning in the worst case

04:35scenario you'll have to touch h number of nodes where h is the height in order to find um a

04:42node by

04:43search query or to add a new node or even to delete a new node so how does that compare

04:49to this tree

04:50uh in reality let me just uh open up a little calculator real fast i just want to show you

04:57so if we do log base 2 because we have a binary search tree not a trinary search tree or

05:05something

05:05log base 2 of the number of nodes 15 it tells us that it should take us no more than

05:11four examinations

05:12to find the node that we're looking for if the tree was perfectly balanced uh and if you if you

05:17if you

05:17notice that's exactly what the height is telling us here if the tree was more imbalanced uh the height

05:23would get really uh bad compared to the number of nodes and it would no longer be considered a log

05:28tree

05:28it would just be you know somewhere in between uh linear time and log time um let's see what else

05:35can

05:35i show you real fast let's do well we did that computation let's do a search through the tree

05:40through a tree that's actually really really bad let's pretend uh that we have a uh a bunch of nodes

05:47here and uh you know i've got an old story that i love to tell about this when my when

05:51my grandma was

05:52alive she was kind of bitter towards the end you know i loved her but uh she used to uh

05:57call the cops

05:58on her neighbors for gossip and at some point in time she got into a feud with uh her neighbor

06:05who was also a bitter old lady um you know towards the end it kind of happens sometimes it sucks

06:11but

06:11it happened and uh i guess the neighbor didn't like my grandma's tree that she had in her backyard

06:16so they fought over it they argued over it and then one day my grandma said she was looking out

06:20the

06:20backyard uh the backyard window to to yell at ducks who were jumping into her pool because she just hated

06:27when the when the ducks went into her pool she was waiting for him to show up she wasn't even

06:32looking at ducks she was just waiting and she saw the other little old lady reach her arm over the

06:37fence

06:37and spray my grandma's tree with some sort of poison then my grandma's tree died and uh i guess you

06:45know my grandma never never got over it i always thought it was like a funny story it was a

06:48little sad

06:48but um she poisoned my grandma's tree so we can kind of do the same thing with the binary search

06:55tree we can give bad data let me show you what happens here if i use this data set on

06:59a regular

06:59binary search tree so we're going to add this node right here it's going to be the 14

07:05and then uh when we add the 19 node i'm just going to duplicate it the 19 is supposed to

07:10be on the

07:10right side of 14 because it's greater than 14 so i'm just going to like you know draw a 19

07:17right here

07:18and a little connecting line

07:24okay then when we add the 24 i'm going to duplicate this node over here where does the 24 go

07:28uh belongs on the right side of the 14 and it also belongs on the right side of the 19

07:34because it's greater than 19 so again we have a node that shows up on the right side let me

07:39remember

07:40to actually fix the 19 so it looks like 24 then when we add the uh 29 it's going to

07:47end up being

07:48the same thing right the 29 is going to end up showing on the right the right the right it's

07:51going

07:51to just be on the right side of the 24 so um if we have bad data we can end

07:58up with a tree that kind

07:58of looks like a straight line um and if you are watching this video from the future after i've posted

08:04my uh all of my data structures videos that i have um you might notice that this looks like

08:10another data structure if you if this if you're watching this right away i haven't posted those

08:15videos just yet but uh just tilt your head to the right a little bit and tell me if that

08:19looks like

08:20something that you recognize it looks like a linked list just like a straight line or even i guess you

08:29could kind of say maybe an array um just like a straight line of data there's no uh you know

08:35there's no splitting of the data so we have the 29 and then the 35 and then uh maybe i'll

08:41just do

08:41one more node only and i'll get rid of that 54 because that's too many nodes

08:46so what happens is if you have you know bad data in your binary search tree then your binary search

08:51tree doesn't actually uh search or add uh insert or remove or anything like that in log time anymore

09:00instead it operates in linear time just like a linked list would meaning uh we would have to scan

09:07through every single node in the entire tree to be sure that some value did not exist well

09:12not exactly but in the worst case scenario we'd have to scan through the whole entire tree

09:20so for example uh let's just look at the the number of nodes real fast we'll say the number

09:25of nodes here is one two three four oh i put two 24s in there oh dearie let me get

09:31that

09:31this is 14 19 24 29 and then i guess i got to make that a 35 oh okay and

09:41then there's a 49 i guess i did

09:42add every single node okay so we added the whole entire data set one two three four five six seven

09:47so there's like seven uh items in the tree so i'm gonna say n is equal to seven the height

09:53also is

09:54seven though so the height is seven notice how if we say that it's always true that a binary search

09:59tree has a time complexity in the worst case of o of h meaning you'd have to go down uh

10:05in the worst

10:05case the number of levels that is equal to the whole entire height of the entire tree

10:09tree that's also the number of nodes in the tree which means uh if i wanted to add let's say

10:13the

10:13number uh i don't know if you wanted to add the number uh 60 60 would end up going down

10:20here and in

10:21order to find where 60 would go we'd have to look at the 14 that's 1 19 24 we'd have

10:27to look at all

10:27these nodes uh that is seven nodes we'd have to examine seven nodes just to figure out where the 60

10:33would go or if we were searching for 60 then you know we'd have to go down that far to

10:38find out

10:38that 60 didn't exist so this is nowhere near a log tree this is a linear tree a linear time

10:44tree

10:45and just uh to to drive the point further um if we did log base two of the number of

10:52nodes in this

10:52case seven notice how it's telling us that we should if it was a log tree if it was perfectly

10:57balanced or a self-balancing tree we should have to touch no more than three nodes in order to find

11:03what we're looking for to search through the tree or to insert a new node or even to delete a

11:07node

11:07but that's not the case here because the tree is really really slow compared to a perfectly balanced

11:13tree so we call this a linear tree it sucks you want to try to avoid that you don't want

11:19your data

11:19to be poisoned um on average your trees won't really look like this if you just have totally

11:24random data but if you think there's a chance that your data might be skewed in some way it's

11:29probably a good idea to upgrade to a self-balancing tree which we're going to talk about later

11:33okay what else can i tell you real fast so we talked about uh searching oh you know why are

11:40these trees considered log time i mean they're really really fast but why let's just uh duplicate

11:46this slide here and i'll move it down one level i just want to kind of show you why this

11:51ends up

11:52being a log time tree okay so why why is this a log time tree suppose for the sake of

11:59argument

11:59we're searching for uh the number 52 so if we're searching for the number 52 we're going to look

12:07at the 37 node the root node and decide where uh would the 52 belong let me actually write that

12:12down

12:12so i don't forget 52 question mark where would the 52 belong it would belong on the right side of

12:18the

12:1837 because it's greater than 37 right which means it's actually impossible that the 52 would be in any of

12:26these other nodes on the left side there's no need to check them we're not going to scan the whole

12:29tree

12:30we're just going to go left or right and ignore the whole other side of the tree

12:34so if you think about it what we just did is with one examination we eliminated half

12:39of the remaining data set or i guess of the initial data set if we're looking at the root node

12:44so then the next thing that we do is we just kind of say okay it belongs on the right

12:47side so we look

12:48at the 59 node and we do the same thing we say where would 52 be would it be on

12:53the left side or the

12:54right side of the 59 node it would be on the left side which means uh we're going to eliminate

12:59from

12:59consideration the entire right subtree of the 59 node so again we're eliminating half of the remaining

13:07data set then we kind of go down here and we look at the 48 we do the same thing

13:12uh 52 belongs on the

13:13right side so we eliminate half of the remaining data set you know and then eventually we do find the

13:1952

13:19and then that's it so if we're eliminating half of the data set with every single just one

13:26examination at a time that's why it ends up being log base 2 in other words if you were getting

13:33twice as close to your destination at every step you took if you're like in a car like running maybe

13:39you're on the moon or something uh then it would be a log time you know uh progress towards your

13:44goal

13:44or eliminating half of the data set at every single step sometimes people see for loops on exams and

13:50stuff when we talk about this um like for i equals zero uh i is less than the data set

13:56uh size like n

13:57and then to advance i it would be like i times equals two so i's jumping uh twice as far

14:04each time

14:05that's the sort of thing that uh makes it log so i'm just going to write down log here real

14:10fast

14:11to drive the point home a little bit more o of log base 2 of n yeah so uh i

14:21guess that's all i

14:22wanted to tell you in this video uh hopefully you feel like an expert in searching now if you want

14:26to see more searching videos leave a comment or something like that but uh yeah uh thank you for

14:32watching and i hope you learned a little bit of stuff and had a little bit of fun i'll see

14:37you in the

14:37next video i'm gonna go find a blueberry muffin

14:44hey everybody thanks for watching this video again from the bottom of my heart i really appreciate

14:49it i do hope you did learn something and have some fun uh if you could do me a please

14:53a small little

14:54favor could you please subscribe and follow this channel or these videos or whatever it is you do

15:00on the current social media website that you're looking at right now um it would really mean the world

15:05to me and it'll help make more videos and grow this community so we'll be able to do more videos

15:10longer videos better videos or just i'll be able to keep making videos in general so please

15:15do do me a kindness and uh and subscribe you know sometimes i'm sleeping in the middle of the night

15:21and i just wake up because i know somebody subscribed or followed it just wakes me up and i get

15:25filled

15:25with joy that's exactly what happens every single time so you could do it as a nice favor to me

15:30or you

15:30could you could troll me if you want to just wake me up in the middle of the night just

15:33subscribe

15:33and then i'll just wake up i promise that's what will happen also uh if you look at the middle

15:40of

15:40the screen right now you should see a qr code which you can scan in order to go to the

15:44website which i

15:45think is also named somewhere at the bottom of this video and it'll take you to my main website where

15:49you

15:49can just kind of like see all the videos i published and the services and tutorials and things that i

15:54offer

15:54and all that good stuff and uh if you have a suggestion for uh uh clarifications or errata or

16:04just future videos that you want to see please leave a comment or if you just want to say hey

16:07what's up what's going on you know just send me a comment whatever i also wake up for those in

16:12the

16:12middle of the night i get i wake up in a cold sweat and i'm like it would really it

16:17really mean the

16:18world to me i would really appreciate it so again thank you so much for watching this video and um

16:24enjoy the cool music as as i fade into the darkness which is coming for us all

17:10and i'll see you in the next video and i'll see you in the next video and i'll see you

17:12in the next video

17:15so

17:24so

17:26so

How to Search in a Binary Search Tree (BST) - Step by Step Explanation with Examples

Category

Transcript

Comments

Recommended