‫So now we're going to do our introduction to trees, and we're going to create our trees with nodes
‫that are similar to a linked list node.
‫The linked list node had member variables of value and next.
‫So let's put this back and change this to a binary tree node.
‫So instead of having next, we'll remove that.
‫I will also change the color.
‫I like to do that when I move to a new data structure so we can keep these things visually separate.
‫But the binary tree node has two pointers left and right, so this is still similar to the linked list
‫node, but instead of having one pointer, that is next.
‫We have two pointers that are left and right.
‫So I'm going to put this back and I'm going to shrink this down and move this up here.
‫And as you would expect, these pointers can point to other binary tree nodes.
‫And if we look at this as we have previously with nodes, that this is similar to nested unordered maps,
‫these three nodes would look something like this.
‫So let's put this back.
‫So the way we've designed our nodes with value left and right, they're set up where they can only point
‫at two other nodes.
‫So if you set it up that way, it's going to be a binary tree.
‫But trees don't have to be binary.
‫You could have this 0.23 nodes or 100 nodes or have it where you could point it to unlimited nodes.
‫But for what we're going to build, each node can only point to two other nodes.
‫And then, of course, these new nodes that we've added can also point to two other nodes themselves.
‫So now let's look at some terminology.
‫This tree here is what is called full and a full tree.
‫Every node either points to zero nodes or two nodes.
‫So if you do something like this.
‫Now you have a node, the seven node that only points to one node, so it is no longer full.
‫So let's remove that.
‫Make it full again.
‫And if we remove these two, it is still full.
‫But it is also something else.
‫It is perfect.
‫With a perfect tree.
‫Any level in the tree that has any nodes is completely filled all the way across.
‫So this is also a perfect tree.
‫But if we remove these two, it is no longer perfect, but it is still full.
‫So let's bring these two back.
‫So a perfect tree is also something else.
‫It is complete.
‫So with a complete tree, you are filling the tree from left to right with no gaps.
‫So if we add a node down here, it is still complete because we are filling the tree from left to right.
‫But it is no longer full and it is no longer perfect.
‫If we add one more node like this, filling this from left to right, it remains complete, but it is
‫now also full.
‫But it is not perfect because we haven't filled it all the way across.
‫So if we do this now, it is full and perfect and complete.
‫So let's focus in on this tree.
‫Drop some of these off.
‫So this note here is a parent.
‫Of these two child nodes.
‫These two child nodes, because they share the same parent are also called siblings.
‫And every node can only have one parent.
‫So if you see something like this where a node has more than one parent than it is not a tree.
‫So let's put this back.
‫And child nodes, of course, can also be parent nodes.
‫Now these nodes at the bottom, they don't have any children.
‫And a node that doesn't have children is called a leaf.
‫All right.
‫That is our intro.
‫Four trees.