6. Binary Trees, Part 1

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Erik Demaine

This is the first of two lectures on binary trees. This lecture discusses binary tree terminology, tree navigation, and dynamic operations. These are explored in two applications: sets and sequences.

License: Creative Commons BY-NC-SA

[ParthPatel-vjzv]

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)

[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.

[prashantsharma]

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

[th]

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!

[pif]

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!

[tarunsinghyadav]

Thanks MIT for providing great content.

[ernesto]

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

[biswanathsingh]

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

[linonator]

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

[sushanthreddy]

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.

[aghahasaan]

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

[suindude]

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.

[originalgamer]

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

[exlife]

so this is newer version of lecture of <<introduction to algorithm>> ?

[mayankdhiman]

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

[krishviz]

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?"

[hoze]

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

[mohammadsalehdehghanpour]

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

[roros]

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

[madoben]

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