Complete Binary Tree

A Complete Binary Tree is a type of binary tree that satisfies some particular set of conditions. These conditions are:

Each level in the complete binary should be completely filled only other than the last level of the Complete Binary Tree. Complete filling of a particular level means that each parent that is present in that particular level should have exactly two children nodes, i.e., the left node and the right node. If any of the parents in a level doesn’t have both the right child and the left then it will not be considered as completely filled.
Another condition that is required for a binary to satisfy in order to be called a Complete Binary Tree is that the last level of the tree should have all the keys as left as possible. That means if a parent node is present in the last level of a Complete Binary Tree then it should have the child as only the left child node.

If any of the binary trees satisfy these two particular conditions mentioned above then that binary tree is labeled as a Complete Binary Tree.

So, now for a better understanding let us write a C++ code for the creation and display of the complete binary tree.

Code:

  // a sample C++ program to create a complete binary tree and print the complete binary tree     #include   #include   using namespace std;    // A macro named SIZE is defined with a value of 50 that will represent the size of the queue that will be required for the various operations  #define SIZE 50    // A class named node is created that will act as a single node of the complete binary tree   class node{      public:    // a variable named data of integer type is created that will hold the data that is present in that particular node of the complete binary tree  int data;    // two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree  node *right,*left;  }; // end of node class    // A class named Queue is created that provide all the utilities of the Queue class  class Queue  {  public:  int front, rear;  int size;  node**array;  };    // A utility function named newNode with one parameter of integer type holding the data is created that will be used to add a new node to the complete binary tree  node* newNode(int data) {    // logic of adding a new node to the complete binary tree  node* temp = new node();  temp->data = data;  temp->left = temp->right = NULL;  return temp;  }    // A utility function named createQueue is written that will be used to create a new Queue  Queue* createQueue(int size){      Queue* queue = new Queue();    queue->front = queue->rear = -1;  queue->size = size;    queue->array = new node*[queue->size * sizeof( node* )];    int i;    // all the elements in the Queue object are initialized with NULL  for (i = 0; i < size; ++i)  queue->array[i] = NULL;    // And in the end an object of the Queue is returned  return queue;  }    // A function named isEmpty is created to check whether the Queue object that is passed as a parameter is Empty or not  int isEmpty(Queue* queue){    return queue->front == -1;  }        // A function named isFull is created to check whether the Queue object that is passed as a paramter is full or not  int isFull(Queue* queue){   return queue->rear == queue->size – 1;  }      // A function named hasOnlyOneItem is created to check whether the Queue object that is passed as a paramter has one element or more  int hasOnlyOneItem(Queue* queue){   return queue->front == queue->rear;   }    // A function named Enqueue is created to add data to the Queue object that is passed as a parameter  void Enqueue(node *root, Queue* queue)  {  if (isFull(queue))  return;    queue->array[++queue->rear] = root;    if (isEmpty(queue))  ++queue->front;  }    // A function named Dequeue is created to remove data from the Queue object that is passed as a parameter  node* Dequeue(Queue* queue)  {  if (isEmpty(queue))  return NULL;    node* temp = queue->array[queue->front];    if (hasOnlyOneItem(queue))  queue->front = queue->rear = -1;  else  ++queue->front;    return temp;  }    // A function named getFront is written to get the front element from the Queue object that is passed as a paramter   node* getFront(Queue* queue){   return queue->array[queue->front];   }    // A utility function named hasBothChild is written to check whether the particular node has both the children nodes present or not  int hasBothChild(node* temp)  {  return temp && temp->left && temp->right;  }    // A Function named insert is written that will be used to insert a new node in the complete binary tree  void insert(node **root, int data, Queue* queue)  {  // Create a new node for given data  node *temp = newNode(data);    // If the tree is empty, initialize the root with new node.  if (!*root)  *root = temp;    else  {  // get the front node of the queue.  node* front = getFront(queue);    // If the left child of this front node doesn’t exist, set the  // left child as the new node  if (!front->left)  front->left = temp;    // If the right child of this front node doesn’t exist, set the  // right child as the new node  else if (!front->right)  front->right = temp;    // If the front node has both the left child and right child,  // Dequeue() it.  if (hasBothChild(front))  Dequeue(queue);  }    // Enqueue() the new node for later insertions  Enqueue(temp, queue);  }    // Standard level order traversal to test above function  // This function will the data associated with all the nodes of the complete binary tree  void levelOrder(node* root)  {  Queue* queue = createQueue(SIZE);    Enqueue(root, queue);    while (!isEmpty(queue))  {  node* temp = Dequeue(queue);    cout<data<<” “;    if (temp->left){  Enqueue(temp->left, queue);  // cout<<“n”;  }    if (temp->right){  Enqueue(temp->right, queue);  // cout<<“n”;  }  }  }    // main function is written to call all these functions and check the functionalities  int main()  {  node* root = NULL;  Queue* queue = createQueue(SIZE);      char ch;                // Do-while loop              // Do part for performing actions              do              // Menu is displayed              // Users enter ‘y’ to continue ‘n’ if              // entered by user , the program terminates                {                    // Menu                    // Display messages                    cout<<“Please Choose one of the Operations::”<>choice;                      // Switch case                    switch (choice) {                      // Case 1                    case 1:                            // Display message                          cout<<“Enter the data that you want to add to the Complete binary tree::”<>key;                          insert(&root,key,queue);                          cout<<“Data Added Successfully.”<>ch;                                  } while (!(ch == ‘N’ || ch == ‘n’));        return 0;  }  //end of the main function  ;>;>;>

Output:

So, in the C++ program that we have written and executed above, we have provided a menu-driven approach to add data in the complete binary tree and also verify the addition operation by printing the data present in the complete binary tree.

Here first we added six nodes to the complete binary tree by calling the insert function that will add or append a new node to the existing complete binary tree. The value for these new nodes of the complete binary tree is taken by the user at the time of adding a node to the complete binary tree. So, the user enters any of the options displayed in the menu and the operation is performed successfully.

So, now let us write code for the Complete Binary Tree in the Java programming language.

Code:

  // a sample Java program to create a complete binary tree and print the complete binary tree       // From the package named util the Scanner class is imported in order to get input from the user from the console  import java.util.Scanner;    // A class named Tree is created that will act as the complete binary tree   class Tree {    // An object of the Node class named root is created that will act as the root of the complete binary tree  Node root;    // A static inner class named Node is created that will act as a single node of the complete binary tree  static class Node {    // A variable named data of integer type is created that will be used to store the actual data in each node of the complete binary tree   int data;    // two variables named right and left of the node type are created that will be used to hold the addresses of the right child node and the left child node of a parent node present on the complete binary tree  Node left, right;    // A constructor of the Node class with one paramter of integer type holding the data is created that will be used to add a new node to the complete binary tree  Node(int data)  {  this.data = data;  this.left = null;  this.right = null;  }  } // end of the inner class Node        // A Function named insertLevelOrder is created to add the elements of the array to the nodes of the complete binary tree  public Node insertLevelOrder(int[] arr, Node root,int i)  {  // Base case for recursion  if (i < arr.length) {  Node temp = new Node(arr[i]);  root = temp;    // insert left child  root.left = insertLevelOrder(arr, root.left,2 * i + 1);    // insert right child  root.right = insertLevelOrder(arr, root.right,2 * i + 2);  }  return root;  }    // A Function named inOrder with one parameter of the Node type that is the root of the complete binary tree is passed to this function  // that will be used to print all the nodes in the complete binary tree in inOrder fashion.  public void inOrder(Node root)  {  if (root != null) {  inOrder(root.left);  System.out.print(root.data + ” “);  inOrder(root.right);  }  }    }//end of the Tree class      // A main Class is written to call all the fucntions of the Tree class  class Main{    // main function  public static void main(String args[])  {    // an object of the Tree class is created that will be used to call all the functions of the Tree class  Tree t2 = new Tree();  int arr[] = new int[8]; //{ 1, 2, 3, 4, 5, 6, 6, 6, 6 };  int index=0;  Scanner sc = new Scanner(System.in);    char ch;                // Do-while loop              // Do part for performing actions              do              // Menu is displayed              // Users enter ‘y’ to continue ‘n’ if              // entered by user , the program terminates                {                    // Menu                    // Display messages                    System.out.print(“Please Choose one of the Operations from the menu Displayed below::”);                    System.out.print(“n”);                    System.out.print(“1. To Insert Data in the Complete binary tree.”);                    System.out.print(“n”);                    System.out.print(“2. To Display Data from the Complete binary tree.”);                    System.out.print(“n”);                                          int choice;                    choice = sc.nextInt();                      // Switch case                    switch (choice) {                      // Case 1                    case 1:                            // Display message                          System.out.print(“Enter the data that you want to add to the Complete binary tree::”);                          System.out.print(“n”);                          int key;                          key=sc.nextInt();                          arr[index] =key;                          index = index + 1;                          System.out.print(“Data Added Successfully.”);                          System.out.print(“n”);                          // Break statement to terminate a case                          break;                      // Case 2                    case 2:                            // Display message                          System.out.print(“Contents of the Complete binary tree are::”);                          System.out.print(“n”);                          t2.root = t2.insertLevelOrder(arr, t2.root, 0);                         t2.inOrder(t2.root);                          // Break statement to terminate a case                          break;                      default:                          // Print statement                          System.out.print(“Please enter a valid option from the menu to proceed further.”);                          System.out.print(“n”);                          // Break statement                          break;                    }                      System.out.print(“n”);                    System.out.print(“Type [N or n] to terminate the program.”);                    System.out.print(“n”);                    System.out.print(“Type [Y or y] to continue the program.”);                    System.out.print(“n”);                    sc.nextLine();                    ch = sc.nextLine().charAt(0);                                  } while (!(ch == ‘N’ || ch == ‘n’));      }  } // end of the main class   

Output:

Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 11 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 23 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 16 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 76 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 43 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 33 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 92 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 31 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations from the menu Displayed below:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 2 Contents of the Complete binary tree are:: 31 76 23 43 11 33 16 92 Type [N or n] to terminate the program. Type [Y or y] to continue the program. n

So, in the Java program that we have written and executed above, we have provided a menu-driven approach to add data in the complete binary tree that will provide two functionalities; one for adding data to the complete binary tree and with the help of the other functions, we can also verify the addition operation by printing the data present in the complete binary tree.

Here, first we added eight nodes having values 31, 76, 23, 43, 11, 33, 16, and 92 respectively to the complete binary tree by calling the insert function that will add or append a new node to the existing complete binary tree but creating a new complete binary tree if the node that is going to be added is the first node that will act as a root of the complete binary tree. The value for these new nodes of the complete binary tree is taken by the user at the time of adding a node to the complete binary tree and is passed as a parameter to the insert function to the complete binary tree’s add function. So, the user enters any of the options displayed in the menu and the operation is performed successfully. If the option added by the user is other than the specified operations; an error message is displayed showing “Please enter a valid option from the menu to proceed further.”. And in order to exit the program, the user needs to add ‘N’ or ‘n’ and to proceed with the program for further options ‘Y’ or ‘y’ is added by the user.

So, now let us write code for the Complete Binary Tree in the Python programming language.

Code:

  # a sample Java program to create a complete binary tree and print the complete binary tree       # A global variable named SIZE is defined with a value of 50 that will represent the size of the queue that will be required for the various operations  SIZE = 50      # A class named node is created that will acts a single node of the complete binary tree   class node:    # A constructor of the Node class with one paramter of integer type holding the data is created that will be used to add a new node to the complete binary tree  def __init__(self, data):    self.data = data  self.right = None  self.left = None    # A class named Queue is created that provide all the utilities of the Queue class  class Queue:    def __init__(self):    self.front = None  self.rear = None  self.size = 0  self.array = []      # A utility function named newNode with one paramter of integer type holding the data is created that will be used to add a new node to the complete binary tree  def newNode(data):    # logic of adding a new node to the complete binary tree  temp = node(data)  return temp    # A utility function named createQueue is written that will be used to create a new Queue  def createQueue(size):    global queue  queue = Queue();  queue.front = queue.rear = -1;  queue.size = size;    # all the elements in the Queue object are initialized with NULL  queue.array = [None for i in range(size)]    # And in the end an object of the Queue is returned  return queue;    # A function named isEmpty is created to check whether the Queue object that is passed as a paramter is Empty or not  def isEmpty(queue):    return queue.front == -1      # A function named isFull is created to check whether the Queue object that is passed as a paramter is full or not  def isFull(queue):    return queue.rear == queue.size – 1;      # A function named hasOnlyOneItem is created to check whether the Queue object that is passed as a paramter has one element or more  def hasOnlyOneItem(queue):    return queue.front == queue.rear;    # A function named Enqueue is created to add data to the Queue object that is passed as a paramter and root of the complete binary tree  def Enqueue(root):    if (isFull(queue)):  return;    queue.rear+=1  queue.array[queue.rear] = root;    if (isEmpty(queue)):  queue.front+=1;      # A function named Dequeue is created to remove data from the Queue object that is passed as a paramter  def Dequeue():    if (isEmpty(queue)):  return None;    temp = queue.array[queue.front];    if(hasOnlyOneItem(queue)):  queue.front = queue.rear = -1;  else:  queue.front+=1    return temp;    # A function named getFront is written to get the front element from the Queue object that is passed as a paramter   def getFront(queue):    return queue.array[queue.front];      #  A utility function named hasBothChild is written to check whether the a particular node has both the children nodes present or not  def hasBothChild(temp):    return (temp and temp.left and  temp.right);      #  A Function named insert is written that will be used to insert a new node in complete binary tree  def insert(root, data, queue):    # Create a new node for  # given data  temp = newNode(data);    # If the tree is empty,  # initialize the root  # with new node.  if not root:  root = temp;  else:    # get the front node of  # the queue.  front = getFront(queue);    # If the left child of this  # front node doesn’t exist,  # set the left child as the  # new node  if (not front.left):  front.left = temp;    # If the right child of this  # front node doesn’t exist, set  # the right child as the new node  elif (not front.right):  front.right = temp;    # If the front node has both the  # left child and right child,  # Dequeue() it.  if (hasBothChild(front)):  Dequeue();    # Enqueue() the new node for  # later insertions  Enqueue(temp);  return root    # Standard level order traversal to test above function  # This function will the data associated with all the nodes of the complete binary tree  def levelOrder(root):    queue = createQueue(SIZE);  Enqueue(root);    while (not isEmpty(queue)):  temp = Dequeue();  print(temp.data, end = ‘ ‘)  if (temp.left):  Enqueue(temp.left);  if (temp.right):  Enqueue(temp.right);    # main function  def main():    root = None    queue = createQueue(SIZE)      while(True):        # Menu          # Display messages  print(“Please Choose one of the Operations::”)  print(“1. To Insert Data in the Complete binary tree.”)  print(“2. To Display Data from the Complete binary tree.”)  print(“n”)                      choice = int(input())    # case 1  if choice==1:  # Display message  print(“Enter the data that you want to add to the Complete binary tree::”)  key = int(input())  root=insert(root, key, queue);  print(“Data Added Successfully.”)          # Break statement to terminate a case  # break    # Case 2  if choice == 2:  # Display message  print(“Contents of the Complete binary tree are::”)  levelOrder(root);  # Break statement to terminate a case  # break                          print(“nType [N or n] to terminate the program.nType [Y or y] to continue the program.n”)  ch=input()                      if ((ch == ‘N’ or ch == ‘n’)):  break      # call to the main function  if __name__ == “__main__”:    main()  

Output:

Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 23 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 76 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 42 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 11 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 30 Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 56 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 68 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 03 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 44 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 1 Enter the data that you want to add to the Complete binary tree:: 17 Data Added Successfully. 1 Enter the data that you want to add to the Complete binary tree:: 28 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Complete binary tree. 2. To Display Data from the Complete binary tree. 2 Contents of the Complete binary tree are:: 23 76 42 11 56 68 3 44 17 28 Type [N or n] to terminate the program. Type [Y or y] to continue the program. N

So, in the Python program that we have written and executed above, we have provided a menu-driven approach to add data in the complete binary tree that will provide two functionalities; one for adding data to the complete binary tree and with the help of the other functions, we can also verify the addition operation by printing the data present in the complete binary tree.

Here first we added nodes to the complete binary tree by calling the insert function that will add or append a new node to the existing complete binary tree but creating a new complete binary tree if the node that is going to be added is the first node that will act as a root of the complete binary tree. The value for these new nodes of the complete binary tree is taken by the user at the time of adding a node to the complete binary tree and is passed as a parameter to the insert function to the complete binary tree’s add function. So, the user enters any of the options displayed in the menu and the operation is performed successfully. If the option added by the user is other than the specified operations an error message is displayed showing “Please enter a valid option from the menu to proceed further.”. And in order to exit the program, the user needs to add ‘N’ or ‘n’ and to proceed with the program for further options ‘Y’ or ‘y’ is added by the user.

So, this article explains the Complete Binary Tree Data Structure and what are the basic functions or operations that we can perform on a Complete Binary Tree. We also understood the usage of the Complete Binary Tree in various programming languages like Java, Python, and C++ along with their functionalities that are required to perform the basic operations on this Data Structure. Other than these examples, there are various scenarios where we can use the Complete Binary Tree.

Next TopicThreaded Binary Tree

Complete Binary Tree

Complete Binary Tree

Code:

Code:

Code:

DS Array representation of Queue

DS | Array vs linked list

You may also like