the Complete Binary Tree vs. the Almost Complete Binary Tree

1.Overview

A binary tree is a popular and commonly used data structure in computer science. A root, a left child (or a subtree), and a right child are all included (or a subtree). In addition, with the exception of leaf nodes, each node can only have two children. There are numerous versions based on this premise.

We'll look at two different types of binary trees in this tutorial: full and virtually complete binary trees.

2. Binary Tree in Its Complete Form

Definition ( 2.1)

When we look at this tree, we can see that all of the internal nodes, except the leaf nodes, have two nodes. Furthermore, all of the leaf nodes D, E, F, and G are on the same level. As a result, we can call this an example of a full binary tree.

2.2. Example

Let’s see some examples:

If we look at this tree, we can see that node C is an internal node rather than a leaf node. Despite the fact that all of the leaf nodes are on the same level, node C only has one child node, which violates the definition. As a result, this example isn't a complete binary tree.

Let’s see another tree example:

3. Binary Tree in Its Complete Form

Definition (3.1)

It is defined in the same way as a binary tree, but with a few additional criteria. Except for the last level, all of the levels of a binary tree are completely filled in a complete binary tree. Nodes may or may not be completely filled in the final level. It's also worth mentioning that all nodes should be filled from the left.

Let us now attempt to simplify it. Each level of a complete binary tree comprises two child nodes. We indicated in the definition that all of the levels are totally filled until the last one. Let's use the letter L to represent a tree's level. If a binary tree is completely filled, there will be 2L nodes at each level.

In our instance, it is absolutely necessary to have two L nodes at each level until the last.

Another concern raised in the specification is that the nodes are filled from the left. As a result, a node cannot have a right child node without also having a left child node.

.3.2. Illustration

Now that we've established the principle, let's test the definition with a few of examples:

All levels except the last should be totally filled, according to the definition. The level mathsf2 is the last level here. At level mathsf0, there is a root node A, and at level mathsf1, there are two nodes B and C. It has met the definition up to this point. It's also worth noting that the nodes are populated from the left.

There are mathsf2 nodes at the level mathsf2. Above all, the nodes are filled from the left. As a result, we can say that it's a complete binary tree.

Let's look at another scenario:

First, we'll see if the given tree has the required number of nodes at each level, with the exception of the last level, which in this case is level mathsf2. We can see that the supplied tree meets this requirement.

After that, we'll see if the nodes are filled from the left. The node B has no sibling nodes at level mathsf2. According to the definition, this is acceptable.

However, there is an issue with this tree because node C has two child nodes. The nodes must now be filled from the left, as per the definition. As a result, there should be a left child node for node B, which is currently absent. As a result, this example deviates from the definition. As a result, it isn't a full binary tree.

Application (3.3).

It's suitable for usage in the heap data structure. There are two types of heaps in computer science: max-heap and min-heap. It's used in sorting algorithms like Heap Sort.

Priority queues and external sorting algorithms are also implemented using it.

4. Binary Tree Nearly Complete

4.1. Clarification

An almost complete binary tree is a type of binary tree in which insertion occurs level by level and from left to right at each level, with the last level not always being entirely filled. Each level, with the exception of the last, has two L nodes.

The essential thing here is that any node that we wish to insert at the lowest level of the tree should be inserted from the left. All of the internal nodes should be filled to the brim.

A binary tree that is virtually complete is also a complete binary tree.

4.2. Illustration

Let's look at a few examples:

This example is identical to the first example of a full binary tree with node G missing. So, at the level mathsf2, we eliminated the node G. It satisfies the definition of a complete binary tree at this moment, if we observe. Is it possible that it is a nearly complete binary tree?

Yes, it is correct. Let's continue the conversation. Because it has the required number of nodes at levels mathsf0 and mathsf1, this sample meets the criterion. The final level in this section is mathsf2. As a result, having all of the 2L nodes at level mathsf2 is not required.

What's interesting to look at now is whether or not the nodes at the lowest level are present in a left-to-right direction. So, node B has two child nodes, D and E, and node C has one child node, F, but it is the left child node. As a result, it meets the concept of a nearly complete binary tree.

Let's look at another scenario:

Notice that this is identical to the first example, except that node F has been removed from the tree.

At each level, we should insert the nodes from left to right, as defined by the definition. We can observe that node C does not have any left child nodes in this scenario. Despite the fact that the node has a right child node, we erased the left child. According to the definition, this is not permitted.

As a result, this is neither a nearly binary tree nor a full tree.