# 6. Binary Trees, Part 1

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=76dhtgZt38A
**Transcript page:** https://www.withtranscript.ai/video/76dhtgZt38A

## Chapters

- 0:12 — Chapter 1 (0:12)
- 4:36 — Chapter 2 (4:36)
- 11:16 — Chapter 3 (11:16)
- 13:32 — Chapter 4 (13:32)
- 15:25 — Chapter 5 (15:25)
- 17:10 — Chapter 6 (17:10)
- 18:43 — Chapter 7 (18:43)
- 21:43 — Chapter 8 (21:43)
- 22:49 — Chapter 9 (22:49)
- 24:41 — Chapter 10 (24:41)
- 26:54 — Chapter 11 (26:54)
- 29:03 — Chapter 12 (29:03)
- 30:35 — Chapter 13 (30:35)
- 31:56 — Chapter 14 (31:56)
- 33:13 — Chapter 15 (33:13)
- 35:01 — Chapter 16 (35:01)
- 39:40 — Chapter 17 (39:40)
- 40:54 — Chapter 18 (40:54)
- 45:19 — Chapter 19 (45:19)
- 47:11 — Chapter 20 (47:11)
- 48:13 — Chapter 21 (48:13)

## Transcript

**[0:12]:** All right, let's get started. Welcome back to double O six. Today we are doing some of the coolest data structures we will see in this class. Maybe some of the coolest data structures ever. Binary trees. You've certainly seen trees in many forms in the past including in this class we've talked used trees as a lower bound tool for in the decision tree model. But this lecture and the next lecture we're going to build one data structure that is almost superior to all data structures we have seen and can do almost anything really fast. First recall all the data structures we've seen so far arrays, linked lists, dynamic arrays, sorted arrays, hash tables and the two sets of operations we're interested in supporting. The two interfaces one was sequences where we're maintaining items in a specified order. We want to be able to insert an item right after another item or delete an item in the middle of the list and always be able to access the ith item.

**[1:13]:** We haven't seen any good data structures for that problem. We're really good at inserting and deleting at the beginning or the end of the sequence but we we haven't seen anything that's efficient at inserting in the middle of the list or deleting in the middle of the list. Linked list you can't even get to the middle in less than linear time. Array you can get to the middle but if you make any changes you have to do the shift which is very expensive. So today or sorry next lecture for the first time we will see all of those operations efficient. Um mention our goal where efficient means logarithmic. So we're not quite as good as linked lists and dynamic arrays at inserting and and deleting at the ends. Those there that we achieve constant or constant amortized time. But up to this log factor we're going to get the best of all worlds where we can solve all the things all the operations that don't build or iterate through the entire structure.

**[2:13]:** That of course takes linear time. But we can do all the others in logarithmic time. For sets sets we're maintain maintaining a bunch of items which have intrinsic keys and we want to search by key. So hash tables are great if you're only doing exact searches. If you want to find a key and get yes or no is it in there and if it's in there give me the item. That's what Python dictionaries do. And they're great at inserting and deleting but they're really bad at find previous and find next. This is the unsuccessful case. If I search for a key and it's not in my structure I would like to know more than just the answer no. I'd like to know what the previous and next items that are actually in the structure. So what are my nearest matches when I search by key?

**[3:01]:** That's a natural query and the only data structure we have that's good at it is a sorted array because binary search gives this to us. If we search for a key by binary search and we don't find it the position that we end up at is right between the previous and next one. But of course sorted arrays are terrible for dynamic operations. We don't know how to maintain we can't maintain a sorted array without any gaps when we're doing insertions and deletions. In some sense today and next class binary trees let us represent a sorted order or in general an order of items dynamically and still allow us to do very fast things like get at of I and find previous of a key. So that's our goal. We're not going to quite get to this goal today. We're going to get uh an incomparable thing called the height of the tree and then on Thursday we'll be able to finish and achieve this goal.

**[3:56]:** Today is just in service to that goal. Um So what is a binary tree? Let me draw an example and then find it more precisely. Mathematicians will call this a rooted binary tree. See in case you've seen that in 042 say. Um Here is a picture.

**[4:36]:** So this is an example of a binary tree. It has a bunch of nodes which we're drawing in circles. It has items in the nodes which we're I'm writing as letters here. So this is item A, item B, item C and it has these links between them. This is like linked lists. Uh but in general a node uh X is going to have a parent pointer uh a left child left pointer and a right child right pointer and it also has uh an item inside of it. So I'm going to talk about node.left is a pointer to the left the node down here. Node.right, node.parent, node.item gives me uh so if I look at the node A its item is A. So let me draw for you

**[5:37]:** some examples.

**[5:53]:** Okay, the parent of A is nothing. So we call A the root node. There's going to be a unique node that has no parent. It's uh sad to have no parents but there you go. Uh then we have node B which whose parent is A. Node C is parent its parent is A. Node D its parent is B. Node E its parent is B and node F its parent is D. Uh um alphabetical order here happens to be ordered by parent. Then we have left pointers. I'll just do a few of them. So left pointer of A is B. Right pointer of A Sorry, B the node. Uh these should all be nodes.

**[6:37]:** I'm circling for nodes and just writing the letter for the item to make it clear that those are different things. Uh the right pointer for A is C. Left pointer for B is D. Right pointer for B is E. And so on. Okay, so in other words each of these lines is a bidirectional pointer. Uh in this direction it's the parent direction in this direction it's left in this case. Um because it's bidirectional we don't draw the arrows. We just draw uh undirected lines. Okay, um this is in general what a binary tree looks like. Uh a key invariant is that if you take a node and say go to its left pointer left child and then go to that node's parent uh this should be the same as node. Right, so that's just saying these are in parent is always the inverse of left or right operation.

**[7:30]:** This is also true for right. Okay, and that's a binary tree. Now the intuition what's going on here is you could you could say it's we're inspired by a linked list. Linked list had a very similar structure. Um maybe an item or there's a node it had an item in it and it had a next pointer and it had a previous pointer. Uh so in some sense what we're if it's doubly linked we had a previous pointer but if singly linked we only had a next pointer. And if you think about the limits of linked lists especially singly linked lists if you just have one pointer per node you can only build a list and so the result is uh you know this this node is going to have depth linear. Depth means how many pointers do I have to follow to get here from the root of the structure which for linked lists was the head.

**[8:29]:** With doubly linked okay I can have a head and a tail and I can put bidirections on here but then still the middle item has depth linear. So there's no way to get there in less than linear time. With binary trees because we use two types of next pointers left and right we can build a tree and we know trees in general have logarithmic can have logarithmic height. Um the and so it's possible in a tree to get to any node starting from the root in only log n traversals. So that's the intuition of what's going on. Now today uh we're going to talk about the height of a tree. So let me define uh I'm going to need a couple definitions here.

**[9:18]:** Subtree and height

**[9:23]:** of a node. Uh so a tree decomposes into subtrees. So for example the subtree rooted at B or the subtree of B is this portion of the tree. Uh so it's that node and all of the descendants of this node. So because we have parents and children we can generalize in the familial tree sense. We can talk about ancestors of a node. So the ancestors of F are its parent, its grandparent, its great grandparents and so on. Together, all of these are called uh ancestors. It's a It doesn't quite correspond to familiar trees cuz familiar trees you have two parents. Here, you only have a unique parent. Or the poor root has no parent. Um We also talk about It's like mixed metaphors. Leaves of the tree. Uh these are uh people with no children. Parents will complain about this, but um many of like many of us in this room, we have no children yet, so we are called leaves.

**[10:34]:** You can tell your parent, "Hey, I'm just a leaf, you know, blowing in the wind." Uh so, uh you know, like this uh it's so many mixed metaphors, but we always draw trees downwards uh like the root structure of a tree, yet we call the ends of the roots leaves, uh which is upside down. Anyway, that's trees for you. Lots of entertaining analogies. Okay, but ancestors are useful. Descendants are also useful. So, the descendants of B are all of its children and all of its grandchildren and all the way down, but just within the subtree. So, subtree of X consists of X uh and its descendants.

**[11:16]:** And we think of X being the root of that subtree. So, we're kind of forgetting about everything outside of the subtree when we talk about subtree of X. Um Let's talk about the depth of a node. Depth of a node is uh I guess the number of its ancestors. That's right. Um The way I usually think of it is the number of number of edges in in the path from X up to the root. So, every node has a unique path that goes upwards until it can't go up anymore. So, the depth of E is two because there are two edges uh one two in the path from the root A to E. So, maybe I'll write some depths. Uh depth of E is two. Depth of these guys is one. Depth of the root is zero. Two. Three. So, those are depths. I'm going to clean this up a little bit.

**[12:39]:** So, we can focus on the image. All right. Height. So, depth is measuring downwards cuz we you know, if you imagine depth within water, this is uh the surface of the water, and then we measure how deep you are from the surface. Height is in the reverse direction. We're going to measure from the leaf level up cuz leaves are at the bottom of the tree. So, height of a node is going to be uh the number of edges in the longest downward path.

**[13:19]:** Okay, which is the same thing as the maximum depth of a node in X's subtree.

**[13:32]:** Uh let's do height in red. So, uh how long is the longest path from F to a leaf? Well, F is a leaf, so all leaves have depth zero. Sorry, height zero. I get it backwards. Um D Here, it's So, there are two ways to go down. This doesn't go to a leaf. Uh this one goes to a leaf, and its height is zero, so this height is one. There's one edge to a leaf here. Uh B has two leaves it can get to. We take the longest one, so that's length two. Uh A similarly has height three.

**[14:16]:** Okay, so height we measure upward, depth we measure downward. What One thing we care about uh is just the height of the overall tree, uh which is the height of the root. And I'm going to call that H cuz we're going to use it a lot.

**[14:39]:** And what we're going to achieve today is all of these running times, instead of being log n, they're going to be order H. So, today our goal is to get all the operations we care about in order H time. And then next lecture, we're going to guarantee that H is always log n, and then we'll get log n time. So, we need to do a bunch of work to achieve log n. Today, we'll do the work that's all the tree manipulation, and as long as your tree is nice and shallow, it doesn't have high height, it has logarithmic height, everything will be log n. Of course, there are trees that are really bad. Right? We can have a tree

**[15:25]:** tree like this, which is basically a linked list, where we only use right pointers, and all the left pointers are null. So, there are high There are trees that are very high, have high height. Um We want to avoid these, but we won't worry about that till next lecture. Question. I have a quick question. Is the height of node C zero? What is the height of node C? Height of node C is zero. Cuz the length of the longest path, the number of edges in the longest downward path is zero. Yeah. We're counting edges, not vertices. Um Yeah. So, the height of the tree is of course just the depth the maximum depth. I think that's right. So, the height here is three, and the maximum depth is this terribly drawn three. So, these happen to correspond in the maximum case, but we use height to always mean maximum, and so that's why we talk about the height of the tree.

**[16:20]:** Depth of the tree is not defined, just depths of nodes. Okay. Um How do we use these trees to represent either sequence or set? Uh I claim that there is a natural order in trees called the traversal order

**[16:47]:** of nodes or items in the tree. So, I'm going to define a particular order. Uh Say in this example, let's do the example first. The traversal order

**[17:10]:** is going to be F, D, B, E, A, C. I feel like I'm in music class. This is the my my guitar or something, but it's not. Help. Just if it is a coincidence. Um So, what is this order? What I'd like to do is um recursively define an order where the root of the tree is somewhere in the middle, and everything in the left subtree is left earlier in the order than the root, and everything in the right subtree is later. So, you can see here, C comes after A, and then all the other nodes come before A. And recursively, if I look at a node B, this node B, which appears over here, E is to the right of it, but if this is all to the left of A, so E is between B and A. B on the left, and then F and D are to the left of that, and again, F comes before D because F is in the left subtree of D.

**[18:14]:** Okay, so we say uh for every node,

**[18:23]:** uh the nodes in X.left are before X, and the nodes in X.right are come after X.

**[18:43]:** And this uniquely defines an order called the traversal order. It's also called the in-order traversal order. It's called in order because it's in the traversal order. So, it's very circular, but um you may have seen in-order traversal, this is the same thing. Uh there's a very simple algorithm for computing this. If I want to iterate uh let's call this Yeah. If I want to iterate all the nodes within a subtree X, rooted by X, um I just iterate on all of the nodes in the left subtree, then I output X itself, then I iterate on all the nodes in the right subtree.

**[19:30]:** Okay, you may have seen that algorithm before. This is just another way to codify the same thing. The result is all the nodes within a subtree appear contiguously with no interruptions, and then the parent parent's going to come before or after, depending on whether it's the left or right child. Okay, so and now it's just a matter of connecting the dots, because we're representing an order. And for sequence, that is going to be the sequence order. If we want to store n items x0 through x1, we're going to build some kind of tree. Uh we're going to put x0 here, x1 here, x2 here, x3 here, x4 here, x5 here. You can see I'm very used to dealing with traversal orders. It takes a little while. Um you could also see it here. We're going to put x1 in this node, x2 Sorry, x0 here, x1 here, x2 here, and so on.

**[20:18]:** That's the same order that I gave. Okay, that's for sequences. For sets, that order is just going to be the sorted order, and we're going to be effectively representing the sorted order of keys, say increasing. Uh but before we get to that, let's talk about different operations we can do uh just playing around with traversal order. And then we're going to use these to build the sequence and set operations that we care about. So, first operation, I'll call subtree first. Seems appropriate that it is called first. Uh It's the first one. So, given a node, which I'll call node, uh this defines a subtree,

**[21:10]:** which usually we draw subtrees as triangles hanging off of the node. It'd be uh So, here I would write x, and then there's some subtree of all the descendants of x. So, with subtree first, I would like to say among all the nodes in this subtree, um which comes first in traversal order?

**[21:43]:** So, just restricting to um that subtree. Subtree of node.

**[21:55]:** So, where is it in this tree? Yeah.

**[22:03]:** Uh node is actually part of many subtrees. Good question. Uh f f is in its own in the subtree of f. Uh f is also in the subtree of d. F is in the subtree of b, like I drew. F is in the subtree of a. It's in in the subtree of exactly its ancestors. But in this operation, when we define node our node only defines one subtree. It is the root of only one subtree. And that's the subtree we're talking about. And then I want to know among all those nodes, which includes node itself and other things, uh which one comes first in this traversal order? This is like practice with traversal orders. So, where should I look for this node?

**[22:49]:** Yeah. The leftmost leaf. Yeah. In the picture, it's here, but pictures can be deceiving. Um we just want to go left as much as possible. When I say go left, I mean this iteration node equals node.left. If you just look at our definition, all the nodes in the left come before x and all the nodes in the right, so it's got to be in the left subtree if there is one. Uh of course, we can't do this forever. Uh so, let's say until we would fall off the tree,

**[23:28]:** which means um node is none. Okay, but we stop uh before that would happen. So, this is like uh the directions like, "Oh, you keep driving until you see the store, and it's the block right before that." And it's like, "Well, that's not very helpful." So, uh you keep iterating node equals node.left until node becomes none, and then you undo one step. Okay, you all know how to program that. It's not hard. Um so, that last non-none node, which might actually be the root. It might be node. Maybe it has no left children. But in that case, I claim node is the very first in its in its subtree traversal order, because if there are no nodes in the left that come before x, then x is actually first. Okay? And that So, that's it. Uh return node.

**[24:22]:** So, I'm modifying node in place here, and the very last one before I hit none, that's the minimum. That's the first item in the traversal order. Similarly, you can define subtree last. Okay, let's do a more interesting one. Successor.

**[24:41]:** Node. So, in this case, I want to know what is the next uh after node in the overall tree's traversal order. Okay, here I was restricting to uh a single subtree. Now, I'm thinking about the entire tree in the entire traversal order. And given a node, I want to know which one comes next. Call this the successor. I feel like I should make some kind of royal family joke now, but I don't know how. Um so, every node has a unique successor. Let's do Let's do some examples. So, we can start with f. The successor of f, if we just index into this list, the successor is d. Okay? Successor of d is b. Successor b is e. It's Okay, it's very easy to read successors off when I have the traversal order written down, but let's think about how to do it in the tree.

**[25:41]:** Okay? Uh Let's see. There are going to be two cases. If I look at the successor of a, it has a right child. And in this case, the right child of a is the successor, but that's not always the case. I don't have a good example. But if I had another node here, let's call it g, uh the successor of a is actually g. Right? Cuz uh all of these items come after a in the order, but which one comes first? The leftmost leaf. Okay, that's the problem we just solved. So, if a has a right child, what we want is the leftmost leaf, the first thing in that subtree. The right subtree. Right child subtree. So, this is case one. If uh node.right, so if we have a right child, then what we want is subtree first

**[26:48]:** of the right child.

**[26:54]:** Okay, great. We can reduce to this other operation. Uh but what if the node doesn't have a right child? So, for example, it could be a leaf. Say we're taking the successor of I mean, it doesn't have to be a leaf. Could be f, which has no children. It could be d, which has one child, but no right child. So, what's the successor of f? Well, it's d, which in this case is the parent, but it's not always. For example, if we do successor of e, its parent is actually earlier in the order, because e was a right child. Here, f was a left child, and so its parent was after. Um Successor of d happens to be b, because uh it's par- it was the left child of its parent. Okay, so that seems like the easy case. If we're the left child of our parent, then our successor is our parent.

**[27:46]:** Okay, basing on this some small example, but we can argue it generally in a moment. What's the successor of e? Uh well, it's not b, cuz that comes earlier. In fact, all the things in this in b's subtree come earlier or equal to e. Um so, we have to keep going up. And then it turns out the successor of e is a, because this subtree was the left child of a, because b was a left child of a. So, the general strategy is walk up the tree until we are we we go up a traversal whose reverse direction would be left. Okay? So, um walk up the tree. When I say walk up, I mean node equals node.parent iteration.

**[28:40]:** Until um we go up a left branch.

**[28:50]:** So, this would mean that node before we do the change, node equals uh node.parent.left.

**[29:03]:** Okay, so we can check that. And then after we do that traversal, that parent is exactly the node we're looking for.

**[29:13]:** Okay, why is this true in general? Let me draw a more generic picture. So, we're starting at some node, and let's say its parent is to the right, so it comes later in the order for a while. Sorry. Get this backwards. We're doing successor.

**[29:34]:** It goes to left for a while. So, these are all these nodes will come earlier in the order, because by the definition, everything in the right subtree comes after. And at some point, we have a parent that's to the right, meaning this node was the left child of this parent, and that node by definition will come after all of the nodes in here. And could there be anything in between node and this uh this parent grandparent ancestor? Uh only if there was something in this subtree. And we're in the case here where there is no right subtree of our original node. So, these this is where all the nodes in between node and here would be, but there aren't any, and therefore this is the successor. So, that's sort of the general argument why this works. I see a question. Yeah.

**[30:35]:** Uh placed into the traversal order. So, the traversal order is never explicitly computed. What we're talk It's always implicit. We can't afford to maintain this as, say, an array. This is just in our heads. Maybe I will draw it with a cloud around it. We're just thinking this. Okay? It's not in the computer explicitly. In the computer, all we store is this. And the reason is this is expensive. We don't We can't maintain an array of things and be able to insert in the middle, whereas this is cheap. I can afford to maintain this structure and do all these things. And so, the reason we're talking about these operations is they're letting us manipulate the order, or in this case letting us iterate through the order. So, this was an algorithm for iterating through the entire order, but that takes linear time. Uh this was getting started in the order, find me the first first thing in the order, and this was given one node, find me the next one.

**[31:35]:** How long do these operations take?

**[31:48]:** Yeah.

**[31:56]:** Right. At most the height of the entire tree. In fact, it's going to be the depth of that first node, but in the worst case that's the height of the entire tree. In general, all of these operations are going to be order H. Uh we need to think about it in each case, except for this one, which is order N. Cuz we're iterating through the whole thing. Um this In this case, we're just calling subtree first, so that takes order H time. Here, we're walking up the tree instead of down, but that's going to cost exactly the height of the node. We happen to stop early, but worst case, order H. For all these all the uh operations we consider today, we just want to get an order H bound, and later we'll we will bound H. So, the point is these are fast. If H is small, like log N, these are almost instantaneous.

**[32:41]:** Whereas if I had to update the explicit traversal order, say as an array, I would have to spend linear time every time I make a change. And yes, it would be fast to do successor if I had this stored explicitly, but maintaining it would be impossible. Maintaining it efficiently would be impossible. Question?

**[33:05]:** Yes. Okay.

**[33:13]:** Cool. Uh so, these were queries where I want to follow uh see what's what's next in the traversal sequence. Now, let's talk about actually changing the traversal sequence. So, these are insert and delete operations. These will correspond roughly to insert at or delete at, but they're not quite We're not quite in sequence world yet. Instead, we're going to focus on inserting or deleting in the middle of a subtree.

**[33:47]:** So, I'm going to have two nodes.

**[33:56]:** So, the

**[34:00]:** in the traversal order So, node already exists in the tree. New is a new node that does not yet exist in the tree, hence I call it new. And what I'd like to do is insert new right after node. Okay? And there's a symmetric operation, which is insert before. It will be implemented almost identically. Um so, we'll just focus on after. So, I want to insert this new node in the traversal order, which again is in our heads. This is all in in our thought bubble. Um that's what we want to achieve, and we have to do it by manipulating this tree, and what however we change the tree, it defines a new traversal order. Uh so, maybe let's do an example first.

**[35:01]:** Actually, yeah, I probably want this traversal order. Keep track of that. So, uh let's say the first thing we want to do uh is insert G before E. I want to illustrate both of the operations. Uh insert H after E. A.

**[35:38]:** Okay. Um So, insert G before E. So, conceptually, what we want to do is insert G here. And the way So, we're given the node E, and we're given a sort of empty node I mean, a node that just contains G. It doesn't have any pointers yet. And we would like to put it before E. Where should I put it? Left child. Right? So, that's This is an easy case. If I'm trying to insert before and there's no left child, stick it there. If you're trying to insert after and there's no right child, stick it there. Easy. So, let me write down case one. Uh So, here we're inserting after. So, if there's no uh right child

**[36:31]:** put new there. Okay? I'm using informal language here, putting this new node um there be instead of writing, for example, node.right equals new. Because that's only one operation you need to do. One thing you would do is set node.right equals to new, but you also have to set new's parent to be node.right. So, instead of worrying about those two pointer changes, cuz we always do bidirectional pointer changes, I'm just going to use pseudocode, and then in recitation you'll see actual Python code that does all this. Uh so, then there's the other case. So, that should be the second example, insert H after A. Right? Insert H after A. So, we already have a node after A in the right child's in this right subtree. Um So, where do I want to put H relative to A? Well, it should be to the right of A, but it should be before C.

**[37:41]:** It should be to the left of C. So, that would mean we want to put it here. And this case it was pretty easy because this tree was small. Where do I want to put it in general? Well, wherever uh subtree first tells me to put it, right? Subtree first is going to give me the successor. These are all kind of parallel. Um We're in the case now where our node has a right child, and then successor tells us where the successor is. It is the first node, which is the leftmost descendant in the right subtree of the node. Okay? A lot of pointers to follow in that sentence, but um it's clear in the picture. So, this In this case, we had node, and there was no right child, so we just added new to be its right child. Okay? In the other case, we had a right child.

**[38:37]:** So, here's node. There's uh there's this node here, node.right, which now we're supposing exists. And it defines a whole subtree. There's this one, which is the first node in the traversal order of this subtree, also known as the successor of node. So, call this successor of node in the current traversal order, but of course we'd like to make new the new successor of the node. So, where does it go? Here.

**[39:17]:** We want to add it as a left child to the old successor. Okay? So, put uh node as uh

**[39:40]:** So, take the successor, and if you look at the code for successor, we're in this case, so we know it will just call subtree first of node.right. And remember, subtree first went left as much as it possibly could. So, what that means is this successor node is guaranteed to not have a left child. Right? Because it was defined by going right once and then going left as much as you could. So, there's no more left, which means we can make one more left. We just add new there and we're done. Now, if you look at the traversal order, it will be node then new then the old successor and then the rest of that subtree. Okay, it's kind of cool. In all cases, uh I mean, this was constant time. Here, we spent constant time after we called successor. Successor costs order H time, so this is order H.

**[40:32]:** Hm? New new. Okay. Put new there.

**[40:44]:** Clear? Okay, that was insertion. Let's do deletion.

**[40:54]:** Get the spec right and the example.

**[41:10]:** All of these are going to have two cases. Uh so, let me Oh, I didn't update. So, now H is after A. So, it should be like this. And you can check the new traversal order of this tree is exactly that. Next, I'm going to do a couple of deletions. Let's delete F first and then we're going to Well, this is confusing.

**[41:47]:** And then we're going to delete A. So, where is F? We're supposing we're given a pointer to F, this node. Well, it's a leaf. So, if I want to delete it, I just erase it. Easy. Leaves are easy to delete. There's no no work to do. So, what that means is I'm removing the pointer from D to F. Okay, we just erase that guy. Uh okay, now here's a trickier one. Suppose I want to delete the root of the tree. This is kind of the hardest case, but in general, it'd be somewhere in between leaf and root. So, if I want to delete A, if I just erased it, then suddenly there are these pointers to nowhere and I disconnect the tree into two parts. I don't want to do that. I need to keep my tree connected. So, I'm going to play this trick, which is I forget if I use successor or predecessor.

**[42:38]:** Predecessor. Um So, I'm going to s- uh look at A. We already have defined successor and thereby predecessor. Uh so, I'm going to look at the predecessor of A, which is E. You can check that here. The one before A is E. This is in the left subtree. Uh find me the rightmost item. Keep going right until I can't. That's E. So, now these guys are adjacent in the order and I'm about to remove A from the order. So, I can momentarily cheat and swap their labels. I'm going to erase A and E here and put E after A. Why? Because it moves A down in the tree. And if I get to the leaf, I'm done. So, I'm not quite done cuz this is not a leaf. So, again, I look at A's predecessor. It's now G. Predecessor um we hope is always in the uh farther down in the tree.

**[43:37]:** And then I swap A with G.

**[43:42]:** Okay, I have preserved the traversal order except where A falls just by moving A earlier in the order here. And now A is a leaf and I can erase it. Okay, so that's what we're going to follow. Now, in actuality, it's a little tricky. Sometimes we need to use predecessor, sometimes we need to use successor. Okay, so the cases are if node is a leaf, uh just detach it from the parent. Easy. That's sort of our base case in the recursion. Otherwise, um there are two cases. If So, if we're not a leaf, that means we have a left child or a right child or both. Both is going to be the easy case. Uh but in general, I have either there's a left child or there's a right child. In either case, I'm going to be happy, so I don't need a a both case.

**[44:40]:** Uh okay, so what do I do? In if I have a left child, that guarantees to me that it the node's predecessor is inside that left subtree, which means it's lower in the tree. If I didn't have a left child, the predecessor would actually be higher in the tree and I don't want to go higher. Okay, so if I have a left child, I know the predecessor is lower and so I'm going to swap my item, contents of my node, with my predecessor's item.

**[45:19]:** And then I'm going to recursively uh delete predecessor.

**[45:32]:** Okay, that's the case that we looked at in this code in this example because we always had a left child. If we have a right child but no left child, we just do the reverse. We swap with our successor's item and then delete the successor. Okay, in either case, we're going down and so if we start at some node like the root, uh every time we do this operation, we're walking down and then we're walking down and in general, we'll keep walking down resuming where we left off, which means total amount of time we spend is proportional to the height of the tree in the worst case. Question?

**[46:15]:** Right. So, E didn't used to have a right child. So, we're changing identities of nodes when we do this cuz we uh This We didn't actually move this circle. The circle stayed in place and what we changed was the item that was stored in that circle. So, whether you call this node E or A, uh it doesn't really matter. It is just the root node. Okay, so we're going to play a lot of these tricks of moving the items around. So far, we hadn't been doing that. We just been creating nodes and placing them somewhere. Uh but now we're uh in this delete operation is the first time where we're changing what's stored in the nodes. But we still can define the traversal order, right? The traversal order of this tree is D B G E H C, which should be what we get here if I delete F and A.

**[47:02]:** And Sorry, can't F.

**[47:11]:** Trees will not preserve connections. That's just the name of the game. We are We have to allow this, otherwise we can't do anything. That's the short version. Okay? Okay, and in the last few minutes, let me talk about how we take these trees and implement a set or sequence. Okay, I've already alluded to this.

**[47:34]:** So, for a sequence,

**[47:40]:** we just make the traversal order equal to the the order that we're trying to represent, the sequence order.

**[47:53]:** And if we're trying to store a set, items with keys, we're going to make the traversal order equal to uh ordered by increasing key. Increasing item key.

**[48:13]:** In some sense, that's it. Uh but then we need to think about how do we implement all of these operations. So, maybe most enlightening is uh for starters is finding a key in a tree. So, uh this is going to correspond to binary search. Right? If I'm searching for a key, let's say I'm searching for G's key and I know it's maybe hard in this example. Maybe I'll replace these all with numbers. So, I can think about key values. Okay, so let's say 1 7 12 17 19 and 23. Um this is now in key order. If you think of the traversal order, the property is that all the keys in the left subtree of the root are less than the root and the root is less than all the keys in the right subtree and recursively all the way down. This is uh something called the binary search tree property, BST property.

**[49:18]:** These uh here we're calling them binary trees sets or set binary trees, uh but they're also known in the literature as binary search trees, term you may have heard before. So, this is a special case of what we're doing where we're storing the keys in order. And then if I want to search for a key like uh 13, I compare that key with the root. I see, oh, it's not equal and it's to the left cuz it's less than 17. So, 13 is left of here. 13 is right of seven. 13 is right of 12. And so, I know that this is where 13 would belong but there's no right child there and so, I know in find I just return nothing. If I was doing find previous, I would return this node because I have tried to go to the right. The The last time before I fell off the tree, I was trying to go to the right and therefore, that last node I had was the previous item.

**[50:12]:** If I was trying to do find next, what would I do? I would just take this node and compute its successor which we already know how to do and that happens to be the root. Okay, so now I can do these inexact searches. When I do find previous and find next, when I fall off the tree, I find either the previous or the next and then with predecessor or successor, I can find the other one. Okay, so that's how we can do find and find previous and find next. To do uh, sequences, we need a little bit more work. We'll do that next time.
