Data structures: Binary Search Tree

See complete series on data structures here:
• Data structures
In this lesson, we have discussed binary search tree data structure. Binary search is an efficient data structure in which we can store data to get search, insertion and deletion, all in O(log n) running time. We have drawn comparison of Binary search tree with arrays and linked list and explained this concept in detail.
For practice problems and more, visit: www.mycodeschoo...
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool

[@supastar25]

I absolutely LOVE how you started off by showing the common operations and their time analysis for Arrays and Linked lists before introducing BST. Sometimes you just know these things but not exactly WHY the need for them in the first place. Thanks.

[@Lyriks_]

totally agree with you

[@ajaysabarish9645]

yours is perhaps the only lectures series that doesn't confuse students with unnecessary things,it is really great,thank you very much

[@ccossmin]

Honestly this was one of the best, if not *the* best algorithm exploration I've ever seen. Congratulations to the author(s)!

[@mrspock7277]

One of the authors died in a hit and run case, back in 2014. It’s really a great loss. The other one is working for google in Silicon Valley.

[@leixun]

*My takeaways:* 1. Computation complexity comparison of searching/inserting/removing elements in Array (sorted, unsorted), linked list and binary search tree (balanced) 0:00 - 9:28 2. What is balanced binary search tree and why it is efficient for searching 9:30 3. Unbalanced binary search tree 16:22 3. Insert and remove elements in balanced binary search tree is also efficient 17:44

[@ArpanPathak]

You are the best teacher in this planet .....

[@zahirjacobs716]

He was. R.I.P.

[@peachyspalace]

Hes dead? Didnt he upload a video 5 months ago?

[@AhmedHadiPADI_scuba_instructor]

are you serious ?

[@zahirjacobs716]

Ahmed Hadi unfortunately I am. Sometime in 2014 already. There is a Quora answer about this written by the cofounder of this channel. Google humblefool.

[@sourabhsingh4058]

@@zahirjacobs716 nop brother he is alive

[@brianspain4252]

You sir are an incredible teacher. Your delivery and pace is so easy to understand. Thank you for the great content.

[@karthikkumaresan1091]

He won't hear you. He passed away in an accident, a year after these lessons came out.🙁

[@temitopeoyeyemi899]

if you have exam this morning skip and start at 9:53

[@saitaruns]

And play the video in 2x

[@akashlenka4068]

@@saitaruns 🌝😅

[@tasty0rang3]

@Ammie Zolman wow! a shady comment posted minutes after, i’m gonna believe this :D

[@piyushagarwal5830]

@@tasty0rang3 lol

[@kirind7181]

thanks dude

[@dineshbhonsle6524]

Very crisp and clear, it was 16 years since i graduated and never brushed up on this topic. Excellent !

[@evanl5299]

Excellent explanation. I wish my university classes were this concise and well-explained.

[@malkavian6275]

One of the best explanations I've seen on any subject, I understand this perfectly now. Thank you!

[@megr]

One of the best videos I've seen regarding data structures. Thanks for sharing the knowledge.

[@sudhirsharma2902]

Man! the teaching level is just amazing. Respect for the knowledge and research behind this level of content-creation. Thanks with all my heart ❤️.

[@karthikkumaresan1091]

He was a pioneer of DS teaching in India but passed away at age 30. ☹

[@UshaPonnada]

You are a great teacher and confident teacher with profound knowledge

[@liliayu]

It's very helpful, Thank you for your explanation

[@RahulKumar-wk2jp]

You all lectures are very simple and understandable...thanks a lot..keep working like that..

[@___vijay___]

You have done something very good. We are getting good knowledge because of you. Thank you.

[@tr2494]

your videos are really helpful , moreover they convey all the info with so much of ease of understanding , and so efficiently , love your work , its great .and thanks from my side and as well as from the whole freshers in my college cause about more than 90% watch these for sure .

[@lpcruz5661]

Do some more computer science stuff. You are articulate and easy to understand. I like it when you repeat to re-enforce the concepts. Well done.

[@MrIglaq]

At 7.22 min u mentioned about inserting element into sorted array by performing 2 steps: 1)- find the position in array (use Binary Search -O(logn)) and 2)- shift all records (O(n)). How overall complexity time is O(n), since we have the sum of O(n)+O(logn)?

[@nihaanali5923]

Better explanation than my university lecturer. Thank you!

[@createprince2093]

This is super great. Your explanations are concise and understandable and the graphics really help. Thanks for making these :) I will definitely be watching more of these data structure lessons!

[@anubhavsinghal9218]

I just checked out your videos on BST and I must say, Thank you very much. That was amazing....I mean now I know the basic functionality of BST.

[@anoniem012]

Very good, thank you! For showing the necessity of learning this first.

[@deepakbhatt799]

Great lecture sir, these 20 mins are worthy. Thank you sir.

[@liemh9290]

There need to be a compiled list of KZbin courses. best ones like this make the list. THERE are too many.

[@photinoman]

Thank you, I just need popcorn to watch the rest of your videos!

[@gloriakinya3986]

Well,, been taught this in an online class and grasped nothing but here, still online am getting it all🤗🤗Thankyou

[@aniruddhashahapurkar9244]

Best explanation I have ever seen for a data structures' concept!

[@hofsepzakharyan5838]

you explain it wonderfully.. subscribed ;)

[@SonuSonu-tk5pk]

why dont u go to ur country and study

[@wisharya]

what a reply man

[@b.f.skinner4383]

You're an amazing teacher, thank you

[@akhilkola8124]

Excellent explanation and its really good videos

[@nikhilchoudhary2955]

Best tutorial for data structures ever had Subscribed:)

[@kranthitech]

Thanks for making this.. cleared some concepts :)

[@prashant3735]

I like your way of teaching....My teachers also study your lectures before coming to class :D

[@avaneeshyadav124]

Nicely Explained in a very excellent way...Thanks Sir

[@pramaynikhade99]

There's so much of clarity....you really eel so enlightened :)

[@MohakNarang07]

As much as i've read so far, a BST cannot contain duplicate values. But at 11:25, you said that the left child can contain a value 'less than or equal to' the value of the parent node. Can someone please clear this confusion. Thanks!

[@mashable8759]

BEST EXPLANATION EVER!

[@pavan.nprabha9724]

Thank u for explain that concept sir.

[@kesharwani.prashant]

Thank you, you have great teaching skills

[@LBC_squared]

Is appending O(1), while an insertion could at worst case be O(n), as you would have to move all the elements back one index?

[@sanatit6429]

Your English is very good.grate job.

[@ashwinikumar3721]

Thanks...You really are a great Teacher

[@trinhdangdang9766]

at 15:30, talking about unbalanced tree, should it be the depth and not the height. "A tree is balanced when, for all nodes the difference between heights of left and right subtree is not greater than 1"?? should it be depth instead of heights?

[@rohitkumar-rb1ds]

Why we don't use vectors instead of linked list to solve dynamic memory allocation problem of array?

[@amirdaneshmand9743]

Great video! But I think there is a inconsistency. Insertion in an array have complexity of worst case O(n) while in linked list it is improved to O(1). Consider inserting an element at the start of array, then you have to shift almost all the array by one element, while in linked list you only modify the links of two elements.

[@isovideo7497]

In the unsorted case, insertion into an array just tacks the new item onto the end of the array, so (assuming the allocated space is larger than the number of defined array elements), this is of order O(1). For a one-directional unsorted linked list insertion at the head of the list is also O(1).

[@georgygursky4303]

Thank you so much! this is a great explanation!

[@jonbikaku6133]

Arey I finally realised that you were trying to say ARRAY instead of arey lol. But really clear explanation. Thanks!

[@kodaph]

Thanks for having a better English than others

[@timalbathiya]

AMAZING explanation. Thanks

[@saiprajeeth]

This video is listed in "Additional Resources For Binary Tress" in UCSD course, Data Structures and Performance.

[@djkwemo]

what do you do if you want to insert an element that is equal to the root element?

[@yashchauhan2234]

Grate communication skill .all videos explain clearly thank you!!!!!!

[@kaushikdr]

What if the array is smaller than the amount of elements we want in the list - then for "insertion", we have to put all the elements into a new array, which will be O(n)!? Also, if we want to insert between two existing elements in an array, won't it be the same time complexity as removal or O(n), since the worst case is shifting n-1 elements?

[@irfan0066]

way to speaking is superb dude...

[@sumitdhingra9520]

Given set of random value, we will need to choose an appropriate value of root to create a balanced BST. How can we do that? Also, as you mentioned, if we add more values to BST the tree will become unbalanced and that will increase the search time. So, can I convert unbalanced tree to balanced form again.?

[@m0elj0n0]

Yes, it is called AVL tree.

[@nabeelsyed8123]

Brother kaafi badiya sanjaya hai aapne

[@JamesBrodski]

Thank you so much! What a great video!

[@neilsen4646]

awesome however why there is no searching and sorting in your Data Structure playlist?

[@sudharakafernando4391]

it helped a lot.Thank you!

[@LAnonHubbard]

Amazingly clear, thanks.

[@baole3508]

thank you very much for video, but what I don't understand that is different between binary search tree and binary balanced search tree.

[@TheGrimReaper0101]

just loved it , very nice video. i hope the implementation part comes soon .

[@dukememo8524]

Very good video, very calming voice gj buddy

[@ruchitakadu5396]

Very helpful...thanku so much sir...great explanation😘

[@tyrisnolam]

@18:33 wouldn't it worth to swap number 17 and number 19 (and after the swap, put 17 on the left, of course) after we found where to insert it?

[@tonie_victor]

There's a discrepancy in the base case of this algorithm, no? This current implementation calculates the height of the tree using the amount of nodes instead of edges. When the array is NULL, we should be returning -1 instead of 0.

[@sociallyactive1]

if n number of elements are used and at each iteration it gets halfed then what will be the big oh of n ? Is it n or n/2?

[@TheVatsri]

You're a savior!

[@anirudhpandey2197]

Osm .. Just one problems sometimes ur subtitle cover the white board 13:49

[@quintusdupreez1]

Great explanation, thank you.

[@SherifYosri]

How is the order of insertion in array O(1) ? What if we want to insert a number in the middle of the array ? In this case we will have to shift all the numbers one cell to the right and then insert the number ! This will be O(n) as I think .

[@TheDQ13]

That's correct. O(1) is only achieved if the element is being inserted into an open bucket.

[@srijanyaprasad]

Thanks a lot ..Very easy to understad

[@0987654321878]

Love your tutorials :) i watch it at 1.5x and brush up almost all my required concepts in just 1 hour :D

[@talhaashraf6459]

At 12:00, isn't it a binary search tree? Because value in leaf node 16 is greater than 8

[@seanodonnell6119]

you are a god to me, sir

[@alexandrosanastasiou1964]

Insertion in an array should cost us O(n) because if you want to insert an element at the first position of an array you have to make (n-1) shifts of all the other elements!

[@mahaknarayansingh1554]

excellent explanation!! thanks.

[@MeharCharanSahai]

Man you are AWESOME !

[@armandnoel3888]

You make my day !

[@SonuSonu-tk5pk]

superb explaination.....

[@sciproject1]

please make videos on m way trees

[@mhafeez]

Awesome. Thanks a lot.

[@amitsaini9473]

please make videos on AVL tree , heap and priority queue

[@anuragsmusic]

He is no more is, he passed away 5 years ago

[@SIDDHARTH181196]

shouldn't the insertion be O(n) because what if we insert it at the middle

[@PurnenduMondal_]

I Want to give You 100 Likes for This. My Mind not Sharp Enough. But After I Repeat this 4 times Then i Understood ....

[@ButerWarrior44]

shouldn't array insertion be 0(n)? if insert() is not at the end of the array then all indexes of all elements must change.

[@techtronics6121]

debatable as array length is fixed so u will have to create a new array in that case

[@bantyburange888]

very nice explation

[@madheehasheik3039]

Nice explanation. .👍👍

[@ssorxross]

You are a god

[@pcpardon]

What will happen if a duplicate record is inserted? where it will go?

[@AaronLittle1576]

Insertion in Array isn't constant time though...

[@dgloria]

ave been using this system since ages, never knew it has a name :D

[@sarahpes32]

wonderful! thank you!! 💙

[@ravindranmenokey7057]

Excellent !!

[@myonlynick]

13:56 why the fraction is equal to 1?

[@redraushan]

Thanks a lot

[@andrewgrebenisan6141]

YOU ARE AMAZING

[@omegafala720]

I did not understand nothing

[@AlokGuptakumar]

BST starts from 9.30

[@kirandhamane6442]

12:04 why would replacing 16 with 12, change the tree being a Binary search tree? would anybody please help me out here ?

[@kirandhamane6442]

Thank you brother I appreciate the help.