6. Binary Trees, Part 1

[@ParthPatel-vj2zv]

0:00 intro 4:00 what is a binary tree 9:10 subtree, depth of a node, height of a node, height of a tree 16:24 traversal order of a tree 20:32 traversal operations 33:13 insert and delete operations 47:20 implementing a set with a tree (BST)

[@shyamtripathi2097]

Thank you. Where can we get the recitation (to see the python code)?

[@dzmitry-lahoda]

deletion kzbin.info/www/bejne/bWfHmaedj9lmbqM

[@nate716]

What strikes me is that these lectures are the exact same as the computer science lectures we get at my very low ranked public university. But the difference is that the students in the room have better GPA and accolades than most students in the country. We all learn the exact same things, but the difference is what we do with this knowledge. That’s what makes MIT different. Thank you for posting this for free. :))

[@knowsomething-b8d]

He came wearing a root shirt. Legend

[@Ayushr0129]

Yeah, it’s now that I am realizing that 😂

[@wisdomkhan]

Thank you very much MIT. Please do not ever stop this life changing work. Those who dream of studying in MIT can fulfil it here.

[@stanfordy9104]

nerd

[@xugeorge7030]

@@stanfordy9104 says someone who literally has stanford in one's username

[@flymykim]

true, but im sure this signals some huge change to how the industry will operate. This knowledge, being taught with this much clarity, used to cost tens of thousands of dollars. it can only mean it no longer does...

[@GaioSonase]

@@flymykim the very same knowledge was always available for pennies on the ivy league dollars. It's not really about the knowledge itself.

[@GaioSonase]

@@flymykim What I am trying to say is that the same knowledge could always be found in any university and even outside of university. The true value isn't really in the knowledge--a library is more than enough for that--but the people, the instruction, and the environment.

[@th2315]

Very engaging and informative class, I look through all the online sources, this is the only high-quality algorithm course that is free and python-based. I learned a lot from it! Loved it!

[@anjanikumarjha209]

are there any data structures course of same quality please suggest

[@sushanthreddy5513]

At 29:17, I think it should be "return node.parent" instead of "return node" as node.parent would then be the first parent with a left-child while moving up the tree.

[@gokulakrishnancandassamy4995]

Exactly, even I thought the same! He even says that it is that parent that will be the successor!

[@prashantsharma312]

Great lecture. I always had confusion about the successor - thanks for the clarification.

[@biswanathsingh1991]

Very interesting and educational course; after searching all internet resources, this is the only excellent, free, Python-based course on algorithms. It taught me a lot of things

[@pif5023]

Thank you for sharing this lesson!! As a self thought professional this really gave me ahas moment! For better or worse I was hired before I could dive deep into algos and these lessons are gold!

[@tarunsinghyadav5477]

Thanks MIT for providing great content.

[@ernesto8738]

I know the comments here get melodramatic but seriously: thanks, it means a lot to have this available

[@linonator]

These classes pay so many dividends. It’s just amazing!

[@jaggis4914]

Thanks MIT. Thank you Erik!

[@aghahasaan]

Thank you so much, what a great lecture, respect from Pakistan!

[@suindude8149]

The depth and the breadth first search would be the representation criteria for the data stored inside the memory thus the Information science has got a great evolution. The most efficient search criteria may be having the best case in case of a particular structure namely BFS would be a faster in time complexity than DFS. BFS could be implemented by using the any directional criteria using Stack as the structural unit.

[@apuravmahajan283]

29:13, should it be return node.parent? i am confused anybody explain please

[@krishviz485]

Can someone clarify "why insert_before and insert_after is required in BST ADT when insert operation takes care of inserting where it belongs to?"

[@andriuscibas]

Because, and that was mentioned in this lecture, the sub-roots can sometimes sort of copy the insert and create several records of the same value. In order to eliminate that possibiity, insert_bf and insert_af is used.

[@charliezhou6514]

the leaf analogy is so funny

[@mikhailkilianovski8024]

🌳Could you provide a justification for why we need to 🔁swap 🔁values while doing deletion instead of just overwriting the value of a current node `A` with a value of node `B` ? We are going to delete🚮 `B` anyway, so why bother writing something there?

[@lucifyer4486]

Thank you for uploading this lecture!

[@madoben3294]

at 30:17 of the video. Aren't we supposed to return node.parent since that is the successor?

[@paulluckner411]

I believe the given notation is not quite clear. While walking upwards we need to check if we are going up a left branch and simultaneously update our current node. If it was a left branch then return the updated/current node.

[@originalgamer4962]

why did we not swapped a with d at (42.11-video) , that would be the leaf node and we could immediately remove the a

[@helloworldcsofficial]

I thought the edges in a binary tree are directional, one-way relationship (parent to child only). Right?

[@hoze540]

43:42 isn't A's predessesor supposed to be b after being swapped with E?

[@apuravmahajan283]

nah, left child comes first for every node

[@mohammadsalehdehghanpour9856]

Is it explained in previous lectures hiw to achieve O(1) for insert first with dynamic array?

[@roros2512]

I think he forgot to explain how to delete in the case if node.right, could anyone please explain this point? thanks! 47:30

[@huzaifakhan_771]

He did explain it. In case of node.right, we swap the node item with its successor because it would be lower in the tree

[@nikachachua5712]

can someone explain pls in dynamic arrays insert/delete_first takes O(1) a , but it have to shift all elements so how is that O(1)?

[@mittunsudhahar634]

You can link another dynamic array to the front of the other dynamic array, and maintain both at the same time. One starts from index 0 and the other goes before 0. The details were mentioned in one of the previous lectures tho. Based on this you get insert/delete first in O(1) amortised time just like ins/del last in a regular dynamic array.

[@ianholloway9493]

@@mittunsudhahar634 Do you mean like a circular array where you can define where the array starts so you can expand the array in both directions when needed.

[@mittunsudhahar634]

@@ianholloway9493 Kind of a similar concept but nah I literally mean two dynamic arrays linked together, the second array allows for insertion/deletion at the front of the array, and every so often you need to rebuild the arrays to reorganise them but that happens few enough times that you can call it amortised O(1). They explain way better than I do in one of their videos.

[@anonymitynone6957]

@@ianholloway9493 I think Mittun Sudhahar says that for example, for an array A, if A[0] is the first but you need to insert a value before A[0], then you can define another array B, that B[i] represents A[-i-1], that like use B[0] to represent A[-1], but you should maintain both A and B. This is a method but seems didn't explain what nika chachua asked

[@exlife9446]

so this is newer version of lecture of ?

[@epicflails5471]

Yo is it just me or does that chalk look super smooth to write with ???

[@suhasdotcom]

@42:46 Hello Professor Demaine. With respect I want to ask that why don't we swap A and successor(A) (H in this case). It'd be much easier to remove that leaf.

[@mayankdhiman5355]

this is where peter parker wanted to go for his graduation.

[@bgspradeep]

very goood lecture

[@RoseS-mf8ye]

41:04 delete

[@jks2110]

isnt the traversal result for the tree FDEBAC? as per inorder traversal

[@paulluckner411]

No, it is FDBEAC. Note, B is before E, similar as A is before C.

[@kunchasaikrishna]

I wonder why can't they use digital white board or with a projector for explanation than black board. Easy to use and explain

[@fgfanta]

I find that the instructor writing on the blackboard while talking gives the perfect pacing. Digital stuff encourages the use of pre-made slides, and they kill pacing. The soft noise of the chalk also contributes to the pacing.

[@pyrocrackermillenium675]

I feel like it also demonstrates a useful skill to the students. Explaining from near-scratch is a useful skill for collaborating in environments without so much established theory.

[@이택영-l9h]

Emotional damage for node A

[@soonshin-sam-kwon]

Thanks a lot.💎🎓🔥💯

[@kafychannel]

thanks a lot was extremely useful

[@hoze540]

actually i get it now, G comes before B

[@im-ls8tm]

1:04

[@Anmol_Kamo]

boht hard

[@angelsandemons]

xD great lec

[@Anmol_Kamo]

normie

[@thinkGrey_]

Thanks

[@humanparaquat69]

What about the non-binary trees? You have to be inclusive

[@ShredST]

Extending a binary tree to having more than two children is pretty straight forward.

[@humanparaquat69]

@@ShredST It was a joke

[@edwardnjogu159]

wait until Twitter sees this

[@glen9620]

@@edwardnjogu159 lmao

[@yunoletmehaveaname]

Gotta learn about them genderfluid trees

[@majid_devops]

"I'm just a leaf you know"

[@NavinY5]

Day 7 present

[@gpullareddy-o7x]

use Internal Pointer Variable

[@hussienalsafi1149]

😊😊😊😊😊😊😊😊🇺🇸🇺🇸🇺🇸🇺🇸

[@roni_castro]

I might be dumb, because I don't understand almost nothing of these MIT lectures. They explain with very few practical or simulation examples, so it's hard to understand

[@AmmarAsmro]

Take the prerequisite courses until 90% of the course is understandable. It is very well explained so I would work on your foundations . We all started in a similar place