A binary tree, is a tree where every node has at most two children. If we look at some sample trees, here's tree one, which has a root right here and the root has two children. The right child has two children, this has one child, this has one child, everything looks good. Here at tree two, we have a root, it has two children. The left child has two children, and the right child has two children. This is also a tree, and is specifically a binary tree. Finally, this last tree, we see here is the root. Tree three, has one, two, three children at the root. Because we found a node that has more than two children, this is not a binary tree. So, when we talk about binary trees, we're going to be specific as I was earlier, about a left child and a right child for every single node. So, here's a left child, here's a root node, and here's the root nodes left child, here's the root node right child. So, T sub L, T sub R, for a given node T. So, we can look at the implementation of how we might implement this in code. This binary tree structure looks nearly identical to our list structure. So, remember in our list, we had a list and then a list node. Here we have a binary tree and a tree node. In our list data structure, we had T & percent data, a data by reference. Here in our tree node, we also have data by reference. In our list we had a list node star and then we had a next pointer. Here we have a left and a right pointer. So, instead of a link list, where a link list has just a single pointer to our next piece of data, a TreeNode has a pointer to our left children and a pointer to our right children. So, it's essentially a linked list, with two pointers at every node, instead of just one. The structure is exactly what you saw in a linked list. This shouldn't be a surprise. So, one property of a binary tree that we're going to talk about is the height of a binary tree. This really does apply to all trees, but we're going to pay a specific attention to the height of binary trees. The height of the binary tree is the number of edges that exists in the longest path from the root to a leaf. So, looking at this tree right here, the longest path is going to contain one, two edges. So, because this path contains two edges, we say the height of this tree or h is equal to two. Here in the second tree, here is our root node. If we take the left child, we see that it's height is only one. We only travel one edge. But we need to find the longest path. So, traveling in the longest path we see one edge here, second edge here, third edge here, fourth edge here. So, height of this tree is four. So, the height of a tree is defined in terms of the number of edges that we travel from the root down to a leaf. One probably that exists of a binary tree is we can have binary trees which are full. A binary tree is full if and only if, the nodes have either zero children or two children. So, if we look at a binary tree and look at every single node, we need to check this has two children, okay. This node has two children, all right. This node has two children, alright. This node has zero children, that's fine. Zero children fine. Zero children, that's fine. Zero children, that's fine. However, if you look this other tree that we've been exploring, the root node has two children, that's fine. This left child has zero, that's fine. This right child also has two, that's fine. This node though, it has only one child. Because it has only one child, we can say that this tree is not a full tree. While the tree here is full. In addition to being full, we might want to talk about a perfect tree. A binary tree is considered perfect, if and only if all of the interior nodes have two children and all of the leaves are at the same level. So, looking at our two-sample trees, we see that all the interior nodes have two children, and here at this last level, all of these leaves are the same level. On the other side here, we have interior node has two children, this is leaf node, it's got zero children. Interior node two children, awesome. Oh, here we have a node that's interior to the tree, it's not a leaf node, but it doesn't have two children. Because of that, it's not perfect. Notice that we can also look at a slightly different version of this first tree that we examined. Suppose I removed this rightmost leaf. Is this tree so perfect? This tree is no longer perfect because notice an interior node has just one child. The last property I want to talk about is a tree being complete. So we consider a binary tree to be complete if and only if, the tree is perfect up until the last level and all the leaves on the last level are pushed to the left. What this means is we have a perfect tree here. So, this is a P of height two. So, it's a perfect tree that has height two. Notice that all of the nodes have two children and all the leaves are at the same level. So, this looks good. Here we have a perfect tree up here. So, we have a P2 right here. But then, underneath the P2, we do have a few extra nodes. So, on our very last level, we have to ask are all of these nodes pushed to the left? In fact they are. So, we have a complete tree if and only if the tree is perfect up until the last level, and on our last level, the few dangling nodes we have are all pushed all the way to the left. We're going to see this idea of a complete tree is extremely important once we start talking about heaps. So, with these definitions, we can have some fun puzzles to ask. So, one puzzle is, is a full tree complete? To answer this, we don't just need yes or no, but we actually need to understand and justify either why it's a yes or find a counterexample, if it's a no. So, is a full tree complete? Well, a full tree just needs to have all of its nodes having zero or two children. So, here's a full tree. So, it's full because it has two children, zero children, two children, zero children, zero children. Is it complete? Well, a complete tree has to be perfect up until the last level, so that is a perfect P1. But then, all of the nodes on the last level have to be pushed to the left. Have this been pushed to the left? They have not been. So this tree is full, but not complete. So, here's an example of a tree that is full but not complete. So, is a full tree complete? No. Is a complete tree full? Well, this one we can look at this example right here. We argue that this was a complete tree. This tree was a perfect tree of height two, with a few nodes at the very end. A complete tree requires us to have every node having two children. Here's a node that just has one child. Because this node has only one child, this complete tree is not full. So, is a complete tree full? Not necessarily. We spend this lecture talking only about the definitions and particular formalities about trees, so we can discuss in detail how these trees work and begin to build complicated data structures with provable runtimes, by understanding the properties of trees we create. So, in the next lectures, we're going to start to dive in more about binary trees, we're going to talk about adding data to binary trees and start to organize data around the idea of a tree to create an awesome data structure, that's going to run faster than array or a list in certain circumstances. I look forward to going through those, and I'll see you there.
