Linked complete binary tree & its creation
A complete binary tree is a binary tree where each level ‘l’ except the last has 2^l nodes and the nodes at the last level are all left-aligned. Complete binary trees are mainly used in heap-based data structures.
The nodes in the complete binary tree are inserted from left to right in one level at a time. If a level is full, the node is inserted in a new level.
Below are some complete binary trees.
1 / \ 2 3 1 / \ 2 3 / \ / 4 5 6
Below binary trees are not complete:
1 / \ 2 3 / / 4 5 1 / \ 2 3 / \ / 4 5 6 / 7
Complete binary trees are generally represented using arrays. The array representation is better because it doesn’t contain any empty slots. Given parent index i, its left child is given by 2 * i + 1, and its right child is given by 2 * i + 2. So no extra space is wasted and space to store left and right pointers is saved. However, it may be an interesting programming question to create a Complete Binary Tree using linked representation. Here Linked means a non-array representation where the left and right pointers(or references) are used to refer left and right children respectively. How to write an insert function that always adds a new node in the last level and at the leftmost available position?
To create a linked complete binary tree, we need to keep track of the nodes in a level order fashion such that the next node to be inserted lies in the leftmost position. A queue data structure can be used to keep track of the inserted nodes.
The following are steps to insert a new node in Complete Binary Tree.
- If the tree is empty, initialize the root with a new node.
- Else, get the front node of the queue.
- …….If the left child of this front node doesn’t exist, set the left child as the new node.
- …….else if the right child of this front node doesn’t exist, set the right child as the new node.
- If the front node has both the left child and right child, Dequeue() it.
- Enqueue() the new node.
Below is the implementation:
C++
// Program for linked implementation of complete binary tree #include <bits/stdc++.h> using namespace std; // For Queue Size #define SIZE 50 // A tree node class node { public : int data; node *right,*left; }; // A queue node class Queue { public : int front, rear; int size; node**array; }; // A utility function to create a new tree node node* newNode( int data) { node* temp = new node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // A utility function 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; for (i = 0; i < size; ++i) queue->array[i] = NULL; return queue; } // Standard Queue Functions int isEmpty(Queue* queue) { return queue->front == -1; } int isFull(Queue* queue) { return queue->rear == queue->size - 1; } int hasOnlyOneItem(Queue* queue) { return queue->front == queue->rear; } void Enqueue(node *root, Queue* queue) { if (isFull(queue)) return ; queue->array[++queue->rear] = root; if (isEmpty(queue)) ++queue->front; } 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; } node* getFront(Queue* queue) { return queue->array[queue->front]; } // A utility function to check if a tree node // has both left and right children int hasBothChild(node* temp) { return temp && temp->left && temp->right; } // Function to insert a new node in 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 void levelOrder(node* root) { Queue* queue = createQueue(SIZE); Enqueue(root, queue); while (!isEmpty(queue)) { node* temp = Dequeue(queue); cout<<temp->data<< " " ; if (temp->left) Enqueue(temp->left, queue); if (temp->right) Enqueue(temp->right, queue); } } // Driver program to test above functions int main() { node* root = NULL; Queue* queue = createQueue(SIZE); int i; for (i = 1; i <= 12; ++i) insert(&root, i, queue); levelOrder(root); return 0; } //This code is contributed by rathbhupendra |
C
// Program for linked implementation of complete binary tree #include <stdio.h> #include <stdlib.h> // For Queue Size #define SIZE 50 // A tree node struct node { int data; struct node *right,*left; }; // A queue node struct Queue { int front, rear; int size; struct node* *array; }; // A utility function to create a new tree node struct node* newNode( int data) { struct node* temp = ( struct node*) malloc ( sizeof ( struct node )); temp->data = data; temp->left = temp->right = NULL; return temp; } // A utility function to create a new Queue struct Queue* createQueue( int size) { struct Queue* queue = ( struct Queue*) malloc ( sizeof ( struct Queue )); queue->front = queue->rear = -1; queue->size = size; queue->array = ( struct node**) malloc (queue->size * sizeof ( struct node* )); int i; for (i = 0; i < size; ++i) queue->array[i] = NULL; return queue; } // Standard Queue Functions int isEmpty( struct Queue* queue) { return queue->front == -1; } int isFull( struct Queue* queue) { return queue->rear == queue->size - 1; } int hasOnlyOneItem( struct Queue* queue) { return queue->front == queue->rear; } void Enqueue( struct node *root, struct Queue* queue) { if (isFull(queue)) return ; queue->array[++queue->rear] = root; if (isEmpty(queue)) ++queue->front; } struct node* Dequeue( struct Queue* queue) { if (isEmpty(queue)) return NULL; struct node* temp = queue->array[queue->front]; if (hasOnlyOneItem(queue)) queue->front = queue->rear = -1; else ++queue->front; return temp; } struct node* getFront( struct Queue* queue) { return queue->array[queue->front]; } // A utility function to check if a tree node // has both left and right children int hasBothChild( struct node* temp) { return temp && temp->left && temp->right; } // Function to insert a new node in complete binary tree void insert( struct node **root, int data, struct Queue* queue) { // Create a new node for given data struct 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. struct 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 void levelOrder( struct node* root) { struct Queue* queue = createQueue(SIZE); Enqueue(root, queue); while (!isEmpty(queue)) { struct node* temp = Dequeue(queue); printf ( "%d " , temp->data); if (temp->left) Enqueue(temp->left, queue); if (temp->right) Enqueue(temp->right, queue); } } // Driver program to test above functions int main() { struct node* root = NULL; struct Queue* queue = createQueue(SIZE); int i; for (i = 1; i <= 12; ++i) insert(&root, i, queue); levelOrder(root); return 0; } |
Java
// Java code for the above approach import java.util.LinkedList; import java.util.Queue; class Node { int data; Node left, right; public Node( int data) { this .data = data; left = right = null ; } } public class CompleteBinaryTree { Node root; public CompleteBinaryTree() { root = null ; } // A utility function to create a new tree node Node newNode( int data) { Node temp = new Node(data); return temp; } // Function to insert a new node in complete binary tree void insert( int data) { // Create a new node for given data Node temp = newNode(data); // If the tree is empty, initialize the root with new node. if (root == null ) { root = temp; return ; } // Create a queue to do level order traversal Queue<Node> q = new LinkedList<>(); q.add(root); // Do level order traversal while (!q.isEmpty()) { Node front = q.peek(); // If the left child of this front node doesn't exist, set the // left child as the new node if (front.left == null ) { front.left = temp; break ; } // If the right child of this front node doesn't exist, set the // right child as the new node else if (front.right == null ) { front.right = temp; break ; } // If the front node has both the left child and right child, // remove it from the queue else { q.remove(); } // Enqueue the left and right children of the current node if (front.left != null ) { q.add(front.left); } if (front.right != null ) { q.add(front.right); } } } // Standard level order traversal to test above function void levelOrder() { if (root == null ) { return ; } Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { Node temp = q.poll(); System.out.print(temp.data + " " ); if (temp.left != null ) { q.add(temp.left); } if (temp.right != null ) { q.add(temp.right); } } } public static void main(String[] args) { CompleteBinaryTree tree = new CompleteBinaryTree(); for ( int i = 1 ; i <= 12 ; i++) { tree.insert(i); } tree.levelOrder(); } } // This code is contributed by ik_7 |
Python3
# Program for linked implementation # of complete binary tree # For Queue Size SIZE = 50 # A tree node class node: def __init__( self , data): self .data = data self .right = None self .left = None # A queue node class Queue: def __init__( self ): self .front = None self .rear = None self .size = 0 self .array = [] # A utility function to # create a new tree node def newNode(data): temp = node(data) return temp # A utility function to # create a new Queue def createQueue(size): global queue queue = Queue(); queue.front = queue.rear = - 1 ; queue.size = size; queue.array = [ None for i in range (size)] return queue; # Standard Queue Functions def isEmpty(queue): return queue.front = = - 1 def isFull(queue): return queue.rear = = queue.size - 1 ; def hasOnlyOneItem(queue): return queue.front = = queue.rear; def Enqueue(root): if (isFull(queue)): return ; queue.rear + = 1 queue.array[queue.rear] = root; if (isEmpty(queue)): queue.front + = 1 ; 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; def getFront(queue): return queue.array[queue.front]; # A utility function to check # if a tree node has both left # and right children def hasBothChild(temp): return (temp and temp.left and temp.right); # Function 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 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); # Driver code if __name__ = = "__main__" : root = None queue = createQueue(SIZE); for i in range ( 1 , 13 ): root = insert(root, i, queue); levelOrder(root); # This code is contributed by Rutvik_56 |
C#
using System; using System.Collections.Generic; class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = right = null ; } } class CompleteBinaryTree { Node root; public CompleteBinaryTree() { root = null ; } // A utility function to create a new tree node Node newNode( int data) { Node temp = new Node(data); return temp; } // Function to insert a new node in complete binary tree void insert( int data) { // Create a new node for given data Node temp = newNode(data); // If the tree is empty, initialize the root with new node. if (root == null ) { root = temp; return ; } // Create a queue to do level order traversal Queue<Node> q = new Queue<Node>(); q.Enqueue(root); // Do level order traversal while (q.Count > 0) { Node front = q.Peek(); // If the left child of this front node doesn't exist, set the // left child as the new node if (front.left == null ) { front.left = temp; break ; } // If the right child of this front node doesn't exist, set the // right child as the new node else if (front.right == null ) { front.right = temp; break ; } // If the front node has both the left child and right child, // remove it from the queue else { q.Dequeue(); } // Enqueue the left and right children of the current node if (front.left != null ) { q.Enqueue(front.left); } if (front.right != null ) { q.Enqueue(front.right); } } } // Standard level order traversal to test above function void levelOrder() { if (root == null ) { return ; } Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count > 0) { Node temp = q.Dequeue(); Console.Write(temp.data + " " ); if (temp.left != null ) { q.Enqueue(temp.left); } if (temp.right != null ) { q.Enqueue(temp.right); } } } // Driver program to test above functions static void Main( string [] args) { CompleteBinaryTree tree = new CompleteBinaryTree(); for ( int i = 1; i <= 12; i++) { tree.insert(i); } tree.levelOrder(); } } // This code is contributed by Vaibhav. |
Javascript
<script> // Program for linked implementation // of complete binary tree // For Queue Size const SIZE = 50; // A tree node class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } class Queue { constructor(size) { this .front = -1; this .rear = -1; this .size = size; this .array = new Array(size); } // Standard Queue Functions isEmpty() { return this .front === -1; } isFull() { return this .rear === this .size - 1; } hasOnlyOneItem() { return this .front === this .rear; } enqueue(root) { if ( this .isFull()) { return ; } this .rear++; this .array[ this .rear] = root; if ( this .isEmpty()) { this .front++; } } dequeue() { if ( this .isEmpty()) { return null ; } let temp = this .array[ this .front]; if ( this .hasOnlyOneItem()) { this .front = this .rear = -1; } else { this .front++; } return temp; } getFront() { return this .array[ this .front]; } } // A utility function to create a new tree node function newNode(data) { return new Node(data); } // A utility function to create a new Queue function createQueue(size) { let queue = new Queue(size); return queue; } // A utility function to check if a tree node has both left and right children function hasBothChild(temp) { return temp && temp.left && temp.right; } // Function to insert a new node in complete binary tree function insert(root, data, queue) { let 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. let front = queue.getFront(); if (!front.left) { front.left = temp; } else if (!front.right) { front.right = temp; } // If the front node has both the left child and right child, Dequeue() it. if (hasBothChild(front)) { queue.dequeue(); } } // Enqueue() the new node for later insertions queue.enqueue(temp); return root; } // Standard level order traversal to test above function function levelOrder(root) { let queue = createQueue(50); queue.enqueue(root); while (!queue.isEmpty()) { let temp = queue.dequeue(); document.write(temp.data); if (temp.left) { queue.enqueue(temp.left); } if (temp.right) { queue.enqueue(temp.right); } } } let root = null ; let queue = createQueue(50); for (let i = 1; i < 13; i++) { root = insert(root, i, queue); } levelOrder(root); </script> |
1 2 3 4 5 6 7 8 9 10 11 12