We will cover the basics of trees in this blog before discussing Full Vs Complete Binary Tree. The basics will cover things like what are trees and the application of trees.

We will further discuss the types of trees. In detail, the blog will further explore the codes for full Vs complete binary tree along with their complexity analysis. So what are you waiting for?🙄 Let's get started!

What are Trees❓

Before jumping into types of trees, we must have a basic understanding of trees. A tree is nothing but a Data Structure made up of nodes joined together through edges. It is of a non-linear type. Each node stores some particular information and is connected to other nodes. A tree is used to store hierarchical information.

Example:

In the given example, 1 is the root node, and 2 and 3 are its child nodes. Similarly, 2 is the root for the next subtree, and 4 and 5 are children. For the right subtree, 3 is the root, and 6 and 7 are child nodes.

Applications of Trees✅

1️⃣Storing hierarchical data.

2️⃣Syntax tree: Depicts the source code of the program.

3️⃣Trees are used in networking problems.

4️⃣Trees are used to store computer file systems.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

What are Binary Trees?🙄

The agenda of this blog is to cover everything about full Vs complete binary tree. Before going into the details, we must first learn about binary trees.

A binary tree is a type of tree that has at most two child nodes. The child nodes are commonly referred to as the left and right child. A node in a binary tree consists of three parts: data, a pointer to the left, and a pointer to the right.

Types of Binary Trees❓

This part of the blog will highlight some of the most frequently used binary tree types.

1️⃣Full binary tree: Every node has 0 or 2 children.

2️⃣Complete binary tree: All levels are filled except possibly the last, and all child nodes are to the left.

3️⃣Perfect binary tree: All internal nodes have two children, and all leaf nodes are at the same level.

4️⃣Balanced binary tree: The absolute difference between the height of the left and right subtree is at most.

5️⃣Degenerate binary tree: Each internal node has only one child node.

Full vs Complete Binary Tree🎯

Now that we have gone through the concepts of trees and binary trees, we are all set to learn the difference between full vs. complete binary trees.

Full Binary Tree⭕

A full binary tree is a type of binary tree in which every node has 0 or 2 children. We can also say that in a full binary tree, all the nodes have two children except the leaf nodes(nodes at the last level). This also implies that no particular order is followed for filling in the nodes in the full binary tree. Also, the leaf nodes might not be at the same level in a full binary tree.

Below is an example of a full binary tree.

Some Important Points⭕

1️⃣If the number of leaf nodes is l, and internal nodes are i, then i=l-1.

2️⃣If the number of leaf nodes is l, and the total number of nodes in the tree is n, then n=2l-1.

3️⃣Let us assume that number of nodes in the tree is n, and the number of leaf nodes is l, then l=(n+1)/2.

4️⃣If the number of internal nodes is l and the number of leaf nodes is l, then l=i+1.

Complete Binary Tree⭕

It is nothing but a type of binary tree in which all levels are filled except possibly the last level. The nodes in the last level of a complete binary tree should be as left as possible. This indicates that a particular order is followed for the filling in nodes in a complete binary tree from left to right. We can draw another inference that the leaf nodes of a complete binary tree must be at the same level. Let us understand the complete binary tree clearly, through an example.

Example 1

In the given binary tree,

1️⃣All levels are filled.

2️⃣All the nodes start from the left.

Hence this is a complete binary tree.

Example 2

This binary tree also satisfies the requirements for a complete binary tree.

Example 3

The second level is not filled in this binary tree, and the nodes are to the right. Hence we can say that it is not a complete binary tree. For a deeper understanding of the full vs. complete binary tree concept, let us go through some more examples.

Example 1️⃣

In the given tree, node 2 and node 3 has only one child, therefore it is not a full binary tree. Also, the nodes are to the right, hence this is not a complete binary tree either.

Example 2️⃣

In this binary tree, all the nodes have 0 or 2 child nodes, but the nodes are to the right. Hence this is a full but not a complete binary tree.

Full vs Complete Binary in a Tabular Form🤷♀️

Full Binary tree

Complete Binary tree

In a full binary tree every node has either 0 or 2 child nodes.

In a complete binary tree, all levels are completely filled except possibly the last level.

There is no particular sequence for filling in nodes.

All nodes should be on the left. This means that there is no node that has a right child but not a left child.

There is no necessity for all leaf nodes to be at the same level.

All leaf nodes must be at the same level.

The tree taken in the codes is as follows

Code to check whether a Tree is a Full Binary Tree or not in C++💻

#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node *newNode(char data) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = data;
node->right = node->left = NULL;
return node;
} /*creating a new node*/
bool FullBt(struct Node *root) {
if (root == NULL){
return true;} /*empty tree is a full binary tree*/
if (root->left == NULL && root->right == NULL){
return true; }/*if node has 0 children it is a full binary tree*/
if ((root->left) && (root->right)){
return (FullBt(root->left) && FullBt(root->right));}
return false; /*not a full binary tree*/}
int main() {
struct Node *root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
if (FullBt(root))
cout << "Full binary tree\n";
else
cout << "Not a full binary tree\n";
}

Code to check whether a Tree is a Full Binary Tree or not in JAVA💻

class Node {
int data;
Node left, right;
Node(int element) {
data = element;
left = right = null;
}
}class full_binary_tree {
Node root;
boolean Fullbt(Node node) {
/*empty tree is a full binary tree */
if (node == null)
return true;
if (node.left == null && node.right == null)
return true;
if ((node.left != null) && (node.right != null))
return (Fullbt(node.left) && Fullbt(node.right));
return false;
} public static void main(String args[]) {
full_binary_tree t = new full_binary_tree();
t.root = new Node(1);
t.root.left = new Node(2);
t.root.right = new Node(3);
t.root.right.left = new Node(4);
t.root.right.right = new Node(5);
t.root.right.left.left = new Node(6);
t.root.right.left.right = new Node(7);
if (t.Fullbt(t.root))
System.out.print("full binary tree");
else
System.out.print("Not a full binary tree");}}

Sample Input

t.root = new Node(1);
t.root.left = new Node(2);
t.root.right = new Node(3);
t.root.right.left = new Node(4);
t.root.right.right = new Node(5);
t.root.right.left.left = new Node(6);
t.root.right.left.right = new Node(7);

Sample Output

Code to check whether a Tree is a Complete Binary Tree or not in C++💻

#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node *newNode(char element) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = element;
node->right = node->left = NULL;
return node;
}
/*number of nodes*/
int nodes(struct Node *root) {
if (root == NULL)
return 0;
return (1 + nodes(root->left) + nodes(root->right));
}
bool Completebt(struct Node *root, int i, int nodes) {
/*empty tree is complete binary tree*/
if (root == NULL)
return true;
if (i >= nodes)
return false;
return (Completebt(root->left, 2 * i + 1, nodes) && Completebt(root->right, 2 * i + 2, nodes));
}
int main() {
struct Node *root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
int totalnodes = nodes(root);
int i = 0;
if (Completebt(root, i, totalnodes))
cout << "Complete binary tree\n";
else
cout << "Not a complete binary tree\n";
}

Code to check whether a Tree is a Complete Binary Tree or not in JAVA💻

class Node {
int data;
Node left, right;
Node(int element) {
data = element;
left = right = null;
}
}
class completebt {
Node root;
/*number of nodes*/
int nodes(Node root) {
if (root == null)
return 0;
return (1 + nodes(root.left) + nodes(root.right));
}
boolean Completetree(Node root, int i, int nodes) {
if (root == null)
return true;
if(i >= nodes)
return false;
return (Completetree(root.left, 2 * i + 1, nodes)
&& Completetree(root.right, 2 * i + 2, nodes));
}
public static void main(String args[]) {
completebt t = new completebt();
t.root = new Node(1);
t.root.left = new Node(2);
t.root.right = new Node(3);
t.root.right.left = new Node(4);
t.root.right.right = new Node(5);
t.root.right.left.left = new Node(6);
t.root.right.left.right = new Node(7);
int totalnodes = t.nodes(t.root);
int i = 0;
if (t.Completetree(t.root, i, totalnodes))
System.out.println("Complete binary tree");
else
System.out.println("Not a complete binary tree");
}
}

Sample Input

t.root = new Node(1);
t.root.left = new Node(2);
t.root.right = new Node(3);
t.root.right.left = new Node(4);
t.root.right.right = new Node(5);
t.root.right.left.left = new Node(6);
t.root.right.left.right = new Node(7);

Sample Output

Complexity Analysis🎯

In this section, we will discuss the time and space complexities of the above-mentioned codes for a deeper understanding.

Time Complexity

The time complexity of any algorithm gives us an idea about the algorithm's execution time as a function of n, where n is the number of inputs.

The time complexity for checking if a tree is a full binary tree or a complete binary tree is O(n), where n is the number of nodes.

Space Complexity

Space complexity is the total amount of extra space the algorithm takes as a function of n.

The space complexity of checking a full or complete binary tree is O(n) due to the stack being used in recursion.

We hope you are now well versed with full Vs complete binary tree🎯

Which tree is balanced, full binary tree or complete binary tree?

A complete binary tree is balanced. The absolute difference between the left and right subtree in a complete binary tree is not more than 1.

Is an empty tree a full binary tree or a complete binary tree?

An empty tree is both a full and complete binary tree.

What can be the maximum height of a binary tree?

If the number of nodes in a binary tree is n, then the maximum height can be n-1.

What is the degree of a binary tree?

The degree of a binary tree is 2.

Conclusion

In this blog we started with the discussion of trees. We explored the concepts of binary trees. We learned full Vs complete binary tree with examples and discussed their properties. For our ease, we also noted the full vs complete binary tree in tabular form. We proceeded with discussing the codes for full vs complete binary tree and their examples.