Binary Trees, Part 1

MIT 6.006 Introduction to Algorithms, lecture 6, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces binary trees, a data structure built from nodes with parent and left and right pointers, and explains why they can reach any item in only a few steps.

Key ideas

The lecture says binary trees can do almost anything really fast. The goal is to keep items in order while still being able to insert, delete, and search quickly. 0:34
Each node holds an item and has three pointers: one to its parent, one to its left child, and one to its right child. The pointers link nodes together, a bit like a linked list. 4:39
Each link goes both ways. If you go to a node's left child and then back up to its parent, you arrive where you started. 7:02
Depth means how many pointers you must follow to get from the root to a node. A linked list can have a node with linear depth, but a binary tree can be built so every node is only a few steps from the root. 8:06
Because a binary tree has two kinds of child pointers, left and right, it can be shaped like a tree instead of a single line. A subtree is a node together with all of its descendants. 8:27

Words to know

node: One box in the structure. It holds an item and pointers to nearby boxes.
root: The top node of the tree. It is the only node with no parent.
depth: How many pointers you must follow from the root to reach a certain node.
subtree: A smaller tree inside a bigger one. It is one node plus all the nodes below it.

Example

Think of a family tree that starts with one grandparent at the top. Each person has a parent link going up and can have children going down, so you can trace a path from the grandparent to any great-grandchild in just a few steps. A single long line of descendants would take many more steps to reach the last person.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains how to measure how deep or tall a node is in a tree, and how a tree can be read in a set order.

Key ideas

A subtree is a node together with all of its descendants, meaning its children, grandchildren, and so on down the tree. We think of that node as the root of the subtree. 11:04
The depth of a node is the number of edges (the lines joining nodes) on the path from that node up to the root. The root has depth 0. 11:28
The height of a node is the number of edges on the longest path going down from that node to a leaf. Height is counted from the bottom up, and a leaf has height 0. 13:07
The height of the whole tree is the height of its root, and it is written as h. Operations on a tree take about order h time, so a shallow tree with small h is fast. 14:21
A binary tree has a natural order called the traversal order, or in-order traversal. A node comes after everything in its left subtree and before everything in its right subtree. 18:24

Words to know

ancestor: Any node above a given node on the path up to the root. A node has only one parent, so its ancestors form a single chain going up.
leaf: A node that has no children. It sits at the bottom end of the tree.
subtree: A smaller tree inside a bigger one. It is one node plus everything below it, and we ignore the rest of the tree when we look at it.
depth: How far a node sits below the root, counted as the number of edges from the node up to the root.

Example

Think of the folders on a computer. A folder inside another folder inside the main folder is deeper, and its depth is how many folder steps you climb to reach the top. The height of a folder is how many levels of folders you must go down before you reach a folder with nothing inside it.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows how to find the first node in a subtree and the next node after any given node, by moving left, right, or up through the tree.

Key ideas

To find the first node in a subtree's traversal order, keep moving to the left child until there is no left child. The last node you reached is the first one. 23:39
If a node has a right child, its successor (the next node in the order) is the first node in its right subtree. You find it by going left as far as possible inside that right subtree. 26:42
If a node has no right child, you walk up the tree from parent to parent. The first time you climb up from a left child, that parent is the successor. 28:40
The simple case is a node that is a left child of its parent. In that case, the parent is its successor. 27:48

Words to know

traversal order: The fixed sequence you get when you visit every node in a tree by a set rule. It is like a numbered list of the nodes.
subtree: A smaller tree inside a bigger one. It is a node plus all the nodes below it, like a branch with its twigs.
successor: The node that comes right after a given node in the traversal order. It is the next item in the list.
ancestor: Any node above a given node on the path up to the top of the tree. A node's parent, its parent's parent, and so on are all its ancestors.

Example

Think of a filing system where folders sit in a tree, and you list them in a fixed order. To find the folder that comes right after a folder, you check whether it has sub-folders inside it. If it does, the next folder is the first one inside it. If it does not, you climb back up until you come out of a branch that you entered from the left, and the folder you reach is the next one.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how to find the next node in a tree's order and how to insert a new node into that order by changing the tree's links.

Key ideas

The traversal order is never written down as a list. It exists only as an idea, and the tree's links are what the computer actually stores. 30:36
Finding the next node or walking through the order costs about the height of the tree. If the tree is short, like about log n tall, these steps are very fast. 32:31
To insert a new node after a node that has no right child, you simply attach the new node as that node's right child. 36:09
If the node already has a right child, the new node goes in as the left child of the old successor. The old successor has no left child, so there is always room there. 39:10
Keeping a plain list in order would be slow, because inserting in the middle means shifting many items. Changing a few links in the tree is cheap. 30:57

Words to know

traversal order: The order you visit every node when you go through the tree in a set pattern, like reading a book from start to finish.
successor: The node that comes right after a given node in the traversal order.
subtree: A smaller tree that sits inside a bigger tree, starting from one node and including everything below it.
height: How many steps you have to go down from the top of the tree to reach the lowest node.

Example

Think of a set of sticky notes where each note says who is next in line, and you read the notes by following the pointers. Adding a new person only means rewriting one or two notes, so the change is quick. Rewriting a whole printed list each time someone joins would take much longer.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:50

This part explains how to delete a node from a binary tree without breaking the tree apart, and how to search a tree for a key.

Key ideas

Deleting a leaf, which is a node with no children, is the easy case. You just erase it and remove the pointer to it from its parent. 41:38
To delete a node that has children, you cannot just erase it, because the tree would split into two pieces. Instead, you swap its item with its predecessor (the item just before it in the traversal order) and then delete the predecessor's spot. 42:20
If the node has a left child, use its predecessor, because the predecessor is always lower in the tree. If there is no left child but there is a right child, use the successor instead, which is also lower. 44:41
Every delete step moves further down the tree, so the total time is about the height of the tree, which is the longest path from the top to the bottom. 45:52
In a binary search tree, keys on the left are smaller than the node and keys on the right are bigger. This lets you search the tree the way you would search a sorted list, and when a search falls off the tree, you can find the previous or next item. 49:09

Words to know

traversal order: The order you visit every node when you walk through the whole tree in a set pattern. The lesson uses it to decide what order the items should be in.
predecessor: The item that comes right before a given item in the traversal order. The lesson uses it as a stand-in when deleting a node that has children.
successor: The item that comes right after a given item in the traversal order. It is the mirror of predecessor.
binary search tree property: The rule that keys on the left of a node are smaller than that node's key, and keys on the right are bigger. It is what makes searching a tree work like binary search.

Example

Think of people standing in a line in order of their height. If the person in the middle leaves, you cannot just leave a gap, because the line would be broken, so the person just before them can step into their spot and the line stays in order. Deleting a node in the tree works the same way: its neighbor in the order moves into its place.

3 checked practice questions for this part are in the app.

← Lecture 4: Hashing · Lecture 7: Binary Trees, Part 2: AVL →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York