Difference Between Full and Complete Binary Trees

Difference Between Full and Complete Binary Tree

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

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

Sample Output

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

You can also try this code with Online Java Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

Sample Output

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

You can also try this code with Online Java Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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.

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

• Binary Tree vs Binary Search Tree
• Constructing a Binary Tree from two Traversal Sequences
• Traversal in Binary Tree 
• Print All Leaf Nodes of a Binary Tree from Left to Right
• Check Whether a Binary Tree is Full Binary Tree or Not.
• Check whether a given Binary Tree is Complete or not
• IEnumerable vs IQueryable

Recommended problems -

• Leaf Nodes in Binary Tree
• Vertical Order Traversal of a Binary Tree
• Binary Array Sorting