Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction📌
2.
What are Trees❓
2.1.
Applications of Trees✅
3.
What are Binary Trees?🙄
3.1.
Types of Binary Trees❓
4.
Full vs Complete Binary Tree🎯
4.1.
Full Binary Tree⭕
4.1.1.
Some Important Points⭕
5.
Complete Binary Tree⭕
6.
Full vs Complete Binary in a Tabular Form🤷‍♀️
7.
Code to check whether a Tree is a Full Binary Tree or not in C++💻
7.1.
Sample Input
7.2.
Sample Output
8.
Code to check whether a Tree is a Full Binary Tree or not in JAVA💻
8.1.
Sample Input
8.2.
Sample Output
9.
Code to check whether a Tree is a Complete Binary Tree or not in C++💻
9.1.
Sample Input
9.2.
Sample Output
10.
Code to check whether a Tree is a Complete Binary Tree or not in JAVA💻
10.1.
Sample Input
10.2.
Sample Output
11.
Complexity Analysis🎯
11.1.
Time Complexity
11.2.
Space Complexity
12.
Frequently Asked Questions
12.1.
Is heap a full binary tree?
12.2.
Which tree is balanced, full binary tree or complete binary tree?
12.3.
Is an empty tree a full binary tree or a complete binary tree?
12.4.
What can be the maximum height of a binary tree?
12.5.
What is the degree of a binary tree?
13.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is the difference between Full and Complete Binary Tree?

Author Akriti Bhan
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction📌

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.

What is the difference between Full and Complete Binary Tree?

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❓

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:

tree

In the given example, 1 is the root node, and 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, andand 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.

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

complete binary tree

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

complete binary tree example 2

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

Example 3

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️⃣

full vs. complete binary tree

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️⃣

full vs. complete binary tree

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

Example

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";
}

Sample Input

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);

Sample Output

output full binary tree

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

output full binary tree

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";
}

Sample Input

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);

Sample Output

output not complete binary tree

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

output not complete binary tree

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🎯

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

Is heap a full binary tree?

No, the heap is a 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.

You can refer to other similar articles as well

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available.
 

Happy Learning Ninja! 🥷

Previous article
Height of a Binary Tree
Next article
Depth First Search
Live masterclass