Skip to main content

Check whether a given binary tree is complete or not

The problem at hand involves determining whether a given binary tree is a complete binary tree or not. A complete binary tree is a binary tree in which all levels are completely filled except possibly for the last level, and the nodes are filled from left to right.

Problem Statement

Given a binary tree, the task is to check if it's a complete binary tree.

Example Scenario

Consider the following binary tree:

          1
         / \
        2   3
       / \   
      4   5
     / \ / \
    6  7 8  9

In this example, the binary tree is not complete since the last level is not completely filled from left to right.

Idea to Solve the Problem

To solve this problem, we can perform a level-order traversal of the binary tree using a queue. While traversing, we keep track of the properties that define a complete binary tree. If any violation is encountered, the tree is not complete.

Pseudocode

isCompleteTree(struct BinaryTree *tree)
{
    // Create a queue for level-order traversal
    
    // Enqueue the root node
    
    // Initialize a flag to indicate if missing nodes are allowed
    
    // Initialize the status as true
    
    // Start the traversal loop
    while (the queue is not empty)
    {
        // Dequeue the front node
        
        // Check if the left child exists
        // If it does, enqueue it
        
        // Check if the right child exists
        // If it does, enqueue it
        
        // Check if the missing nodes are allowed
        // Update the flag accordingly
        
        // If there are missing nodes and the flag is true,
        // update the status to false
        
        // If there are missing nodes and the flag is false,
        // update the status to false
        
        // Repeat for all nodes in the current level
    }
    
    // Display tree elements using inorder traversal
    
    // Print whether the tree is complete or not
}

Algorithm Explanation

  1. Implement the isCompleteTree function that takes the binary tree as input.
  2. Create a queue using the makeQueue function.
  3. Enqueue the root node into the queue.
  4. Initialize a flag missingNodesAllowed as true. This flag keeps track of whether missing nodes are allowed in the current level.
  5. Initialize the status of the tree as true. This status will be updated to false if any violation is encountered.
  6. Start a loop that continues while the queue is not empty.
  7. Inside the loop, dequeue the front node from the queue.
  8. Check if the left child of the current node exists. If it does, enqueue it into the queue.
  9. Check if the right child of the current node exists. If it does, enqueue it into the queue.
  10. Update the missingNodesAllowed flag based on the existence of children.
  11. If there are missing nodes and the missingNodesAllowed flag is true, update the status to false, as missing nodes are not allowed in a complete binary tree.
  12. If there are missing nodes and the missingNodesAllowed flag is false, update the status to false, as a complete binary tree should be filled from left to right.
  13. Repeat this process for all nodes in the current level.
  14. After the loop ends, use an inorder traversal to display the tree elements.
  15. Print whether the tree is complete or not based on the status.

Code Solution

/*
    C Program 
    Check whether a given binary tree is complete or not
*/
#include <stdio.h>
#include <stdlib.h>

//Queue node
struct QueueNode
{
	int level;
	struct TreeNode *element;
	struct QueueNode *next;
};
// Define queue
struct MyQueue
{
	struct QueueNode *front;
	struct QueueNode *tail;
};
// Binary Tree node
struct TreeNode
{
	int data;
	struct TreeNode *left, *right;
};
struct BinaryTree
{
	struct TreeNode *root;
};
struct MyQueue *makeQueue()
{
	// Create dynamic node of MyQueue
	struct MyQueue *node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
	if (node == NULL)
	{
		printf("\n Memory Overflow, when creating a new Queue\n");
	}
	else
	{
		node->front = NULL;
		node->tail = NULL;
	}
	return node;
}
// Returns a new node of tree
struct TreeNode *newNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
struct BinaryTree *makeTree()
{
	// Create dynamic node of BinaryTree
	struct BinaryTree *node = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
	if (node == NULL)
	{
		printf("\nMemory Overflow, when creating a new BinaryTree\n");
	}
	else
	{
		node->root = NULL;
	}
	return node;
}
int isEmpty(struct MyQueue *queue)
{
	if (queue == NULL || queue->front == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// Create a queue node and returns this node
void enqueue(struct MyQueue *queue, struct TreeNode *tree_node)
{
	// Make a new Queue node
	struct QueueNode *new_node = (struct QueueNode *) malloc(sizeof(struct QueueNode));
	if (new_node != NULL)
	{
		// Set node values
		new_node->element = tree_node;
		new_node->next = NULL;
		if (queue->front == NULL)
		{
			queue->front = new_node;
			queue->tail = queue->front;
		}
		else
		{
			queue->tail->next = new_node;
			queue->tail = new_node;
		}
	}
	else
	{
		printf("\nMemory Overflow, when creating a new Queue Node\n");
	}
}
//Remove a queue elements
void dequeue(struct MyQueue *queue)
{
	if (isEmpty(queue) == 0)
	{
		struct QueueNode *remove = queue->front;
		if (queue->front == queue->tail)
		{
			queue->tail = NULL;
		}
		queue->front = queue->front->next;
		remove->element = NULL;
		remove->next = NULL;
		//free node
		free(remove);
		remove = NULL;
	}
}
// Return front element of queue
struct TreeNode *peek(struct MyQueue *queue)
{
	if (isEmpty(queue) == 1)
	{
		return NULL;
	}
	else
	{
		return queue->front->element;
	}
}
// Display tree elements
void inorder(struct TreeNode *node)
{
	if (node != NULL)
	{
		inorder(node->left);
		printf("  %d", node->data);
		inorder(node->right);
	}
}
// Determine whether given binary tree is complete binary tree or not
void isCompleteTree(struct BinaryTree *tree)
{
	int status = 0;
	struct TreeNode *node = tree->root;
	if (node == NULL)
	{
		// When tree is empty
		status = 1;
	}
	else
	{
		// Assume that initial tree is complete tree
		status = 1;
		// This is used to track missing child nodes
		int tracker = 0;
		// Create a queue
		struct MyQueue *q = makeQueue();
		// Add first node of tree
		enqueue(q, node);
		// Execute loop until queue is not empty
		while (node != NULL)
		{
			if (status == 1)
			{
				if (node->left != NULL && node->right != NULL)
				{
					if (tracker > 0)
					{
						// When already missing one child or
						// We already reached a leaf node
						status = 0;
					}
					else
					{
						// When both child exist
						enqueue(q, node->left);
						enqueue(q, node->right);
					}
				}
				else if (node->left != NULL || node->right != NULL)
				{
					// When one child exists
					tracker++;
					if (tracker == 1)
					{
						if (node->right != NULL)
						{
							// Because left subtree are empty
							status = 0;
						}
						else
						{
							// Allow first time left subtree 
							enqueue(q, node->left);
						}
					}
					else
					{
						// When more than one child nodes are missing
						status = 0;
					}
				}
				else
				{
					// Get a leaf node
					tracker = 1;
				}
			}
			// Remove a queue element
			dequeue(q);
			// Get front element of queue
			node = peek(q);
		}
		// Display tree elements
		inorder(tree->root);
		if (status == 1)
		{
			printf("\n  Complete Binary Tree\n");
		}
		else
		{
			printf("\n  Not a Complete Binary Tree\n");
		}
	}
}
int main(int argc, char
	const *argv[])
{
	// Define tree
	struct BinaryTree *tree = makeTree();
	/*
              1
            /   \
           2     3
         /   \     
        4     5  
       / \   / \
      6   7 8   9
  
    -----------------------
        Binary Tree
    -----------------------
    */
	tree->root = newNode(1);
	tree->root->left = newNode(2);
	tree->root->right = newNode(3);
	tree->root->left->left = newNode(4);
	tree->root->left->right = newNode(5);
	tree->root->left->left->left = newNode(6);
	tree->root->left->left->right = newNode(7);
	tree->root->left->right->left = newNode(8);
	tree->root->left->right->right = newNode(9);
	isCompleteTree(tree);
	tree->root->right->left = newNode(-1);
	tree->root->right->right = newNode(-2);
	/*
    After add new nodes : -1,-2
    -----------------

               1
              /  \ 
             /    \  
            /      \
           2        3
         /   \     / \  
        4     5  -1  -2
       / \   / \
      6   7 8   9
  
    -----------------------
        Binary Tree
    -----------------------
    */
	isCompleteTree(tree);
	return 0;
}

Output

  6  4  7  2  8  5  9  1  3
  Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
  Complete Binary Tree
/*
    Java Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QueueNode
{
	public TreeNode element;
	public QueueNode next;
	public QueueNode(TreeNode element)
	{
		this.element = element;
		this.next = null;
	}
}
//Define custom queue class
class MyQueue
{
	public QueueNode front;
	public QueueNode tail;
	public MyQueue()
	{
		this.front = null;
		this.tail = null;
	}
	//Add a new node at last of queue
	public void enqueue(TreeNode element)
	{
		QueueNode new_node = new QueueNode(element);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	public void dequeue()
	{
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	public boolean is_empty()
	{
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	public TreeNode peek()
	{
		if (is_empty() == false)
		{
			return this.front.element;
		}
		else
		{
			return null;
		}
	}
}
// Define Binary Tree 
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	public void inorder(TreeNode node)
	{
		if (node != null)
		{
			inorder(node.left);
			System.out.print("  " + node.data);
			inorder(node.right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	public void isCompleteTree()
	{
		// Assume that initial tree is complete tree
		boolean status = true;
		TreeNode node = this.root;
		if (node != null)
		{
			// This is used to track missing child nodes
			int tracker = 0;
			// Create a queue
			MyQueue q = new MyQueue();
			// Add first node of tree
			q.enqueue(node);
			// Execute loop until queue is not empty
			while (node != null)
			{
				if (status == true)
				{
					if (node.left != null && node.right != null)
					{
						if (tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							status = false;
						}
						else
						{
							// When both child exist
							q.enqueue(node.left);
							q.enqueue(node.right);
						}
					}
					else if (node.left != null || node.right != null)
					{
						// When one child exists
						tracker++;
						if (tracker == 1)
						{
							if (node.right != null)
							{
								// Because left subtree are empty
								status = false;
							}
							else
							{
								// Allow first time left subtree 
								q.enqueue(node.left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							status = false;
						}
					}
					else
					{
						// Get a leaf node
						tracker = 1;
					}
				}
				// Remove a queue element
				q.dequeue();
				// Get front element of queue
				node = q.peek();
			}
			// Display tree elements
			inorder(this.root);
			if (status == true)
			{
				System.out.print("\n Complete Binary Tree\n");
			}
			else
			{
				System.out.print("\n Not a Complete Binary Tree\n");
			}
		}
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
                  1
                /   \
               2     3
             /   \     
            4     5  
           / \   / \
          6   7 8   9
      
        -----------------------
            Binary Tree
        -----------------------
        */
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.left.left = new TreeNode(6);
		tree.root.left.left.right = new TreeNode(7);
		tree.root.left.right.left = new TreeNode(8);
		tree.root.left.right.right = new TreeNode(9);
		// Check
		tree.isCompleteTree();
		tree.root.right.left = new TreeNode(-1);
		tree.root.right.right = new TreeNode(-2);
		/*
        After add new nodes : -1,-2
        -----------------

                   1
                  /  \ 
                 /    \  
                /      \
               2        3
             /   \     / \  
            4     5  -1  -2
           / \   / \
          6   7 8   9
      
        -----------------------
            Binary Tree
        -----------------------
        */
		tree.isCompleteTree();
	}
}

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
// Queue Node
class QueueNode
{
	public: 
    TreeNode *element;
	QueueNode *next;
	QueueNode(TreeNode *element)
	{
		this->element = element;
		this->next = NULL;
	}
};
//Define custom queue class
class MyQueue
{
	public: QueueNode *front;
	QueueNode *tail;
	MyQueue()
	{
		this->front = NULL;
		this->tail = NULL;
	}
	//Add a new node at last of queue
	void enqueue(TreeNode *element)
	{
		QueueNode *new_node = new QueueNode(element);
		if (this->front == NULL)
		{
			//When first node of queue
			this->front = new_node;
		}
		else
		{
			//Add node at last position
			this->tail->next = new_node;
		}
		this->tail = new_node;
	}
	//Delete first node of queue
	void dequeue()
	{
		if (this->front != NULL)
		{
			if (this->tail == this->front)
			{
				this->tail = NULL;
				this->front = NULL;
			}
			else
			{
				this->front = this->front->next;
			}
		}
	}
	bool is_empty()
	{
		if (this->front == NULL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	TreeNode *peek()
	{
		if (this->is_empty() == false)
		{
			return this->front->element;
		}
		else
		{
			return NULL;
		}
	}
};
// Define Binary Tree
class BinaryTree
{
	public: TreeNode *root;
	BinaryTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	void inorder(TreeNode *node)
	{
		if (node != NULL)
		{
			this->inorder(node->left);
			cout << "  " << node->data;
			this->inorder(node->right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	void isCompleteTree()
	{
		// Assume that initial tree is complete tree
		bool status = true;
		TreeNode *node = this->root;
		if (node != NULL)
		{
			// This is used to track missing child nodes
			int tracker = 0;
			// Create a queue
			MyQueue q = MyQueue();
			// Add first node of tree
			q.enqueue(node);
			// Execute loop until queue is not empty
			while (node != NULL)
			{
				if (status == true)
				{
					if (node->left != NULL && node->right != NULL)
					{
						if (tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							status = false;
						}
						else
						{
							// When both child exist
							q.enqueue(node->left);
							q.enqueue(node->right);
						}
					}
					else if (node->left != NULL || node->right != NULL)
					{
						// When one child exists
						tracker++;
						if (tracker == 1)
						{
							if (node->right != NULL)
							{
								// Because left subtree are empty
								status = false;
							}
							else
							{
								// Allow first time left subtree
								q.enqueue(node->left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							status = false;
						}
					}
					else
					{
						// Get a leaf node
						tracker = 1;
					}
				}
				// Remove a queue element
				q.dequeue();
				// Get front element of queue
				node = q.peek();
			}
			// Display tree elements
			this->inorder(this->root);
			if (status == true)
			{
				cout << "\n Complete Binary Tree\n";
			}
			else
			{
				cout << "\n Not a Complete Binary Tree\n";
			}
		}
	}
};
int main()
{
	BinaryTree tree = BinaryTree();
	/*
	                  1
	                /   \
	               2     3
	             /   \     
	            4     5  
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	tree.root = new TreeNode(1);
	tree.root->left = new TreeNode(2);
	tree.root->right = new TreeNode(3);
	tree.root->left->left = new TreeNode(4);
	tree.root->left->right = new TreeNode(5);
	tree.root->left->left->left = new TreeNode(6);
	tree.root->left->left->right = new TreeNode(7);
	tree.root->left->right->left = new TreeNode(8);
	tree.root->left->right->right = new TreeNode(9);
	// Check
	tree.isCompleteTree();
	tree.root->right->left = new TreeNode(-1);
	tree.root->right->right = new TreeNode(-2);
	/*
	        After add new nodes : -1,-2
	        -----------------
	                   1
	                  /  \ 
	                 /    \  
	                /      \
	               2        3
	             /   \     / \  
	            4     5  -1  -2
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	tree.isCompleteTree();
	return 0;
}

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree
// Include namespace system
using System;
/*
    C# Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
public class QueueNode
{
	public TreeNode element;
	public QueueNode next;
	public QueueNode(TreeNode element)
	{
		this.element = element;
		this.next = null;
	}
}
//Define custom queue class
public class MyQueue
{
	public QueueNode front;
	public QueueNode tail;
	public MyQueue()
	{
		this.front = null;
		this.tail = null;
	}
	//Add a new node at last of queue
	public void enqueue(TreeNode element)
	{
		QueueNode new_node = new QueueNode(element);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	public void dequeue()
	{
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	public Boolean is_empty()
	{
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	public TreeNode peek()
	{
		if (is_empty() == false)
		{
			return this.front.element;
		}
		else
		{
			return null;
		}
	}
}
// Define Binary Tree
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	public void inorder(TreeNode node)
	{
		if (node != null)
		{
			inorder(node.left);
			Console.Write("  " + node.data);
			inorder(node.right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	public void isCompleteTree()
	{
		// Assume that initial tree is complete tree
		Boolean status = true;
		TreeNode node = this.root;
		if (node != null)
		{
			// This is used to track missing child nodes
			int tracker = 0;
			// Create a queue
			MyQueue q = new MyQueue();
			// Add first node of tree
			q.enqueue(node);
			// Execute loop until queue is not empty
			while (node != null)
			{
				if (status == true)
				{
					if (node.left != null && node.right != null)
					{
						if (tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							status = false;
						}
						else
						{
							// When both child exist
							q.enqueue(node.left);
							q.enqueue(node.right);
						}
					}
					else if (node.left != null || node.right != null)
					{
						// When one child exists
						tracker++;
						if (tracker == 1)
						{
							if (node.right != null)
							{
								// Because left subtree are empty
								status = false;
							}
							else
							{
								// Allow first time left subtree
								q.enqueue(node.left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							status = false;
						}
					}
					else
					{
						// Get a leaf node
						tracker = 1;
					}
				}
				// Remove a queue element
				q.dequeue();
				// Get front element of queue
				node = q.peek();
			}
			// Display tree elements
			inorder(this.root);
			if (status == true)
			{
				Console.Write("\n Complete Binary Tree\n");
			}
			else
			{
				Console.Write("\n Not a Complete Binary Tree\n");
			}
		}
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		                  1
		                /   \
		               2     3
		             /   \     
		            4     5  
		           / \   / \
		          6   7 8   9
		      
		        -----------------------
		            Binary Tree
		        -----------------------
		        
		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.left.left = new TreeNode(6);
		tree.root.left.left.right = new TreeNode(7);
		tree.root.left.right.left = new TreeNode(8);
		tree.root.left.right.right = new TreeNode(9);
		// Check
		tree.isCompleteTree();
		tree.root.right.left = new TreeNode(-1);
		tree.root.right.right = new TreeNode(-2);
		/*
		        After add new nodes : -1,-2
		        -----------------
		                   1
		                  /  \ 
		                 /    \  
		                /      \
		               2        3
		             /   \     / \  
		            4     5  -1  -2
		           / \   / \
		          6   7 8   9
		      
		        -----------------------
		            Binary Tree
		        -----------------------
		        
		*/
		tree.isCompleteTree();
	}
}

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree
<?php
/*
    Php Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
// Queue Node
class QueueNode
{
	public $element;
	public $next;

	function __construct($element)
	{
		$this->element = $element;
		$this->next = null;
	}
}
//Define custom queue class
class MyQueue
{
	public $front;
	public $tail;

	function __construct()
	{
		$this->front = null;
		$this->tail = null;
	}
	//Add a new node at last of queue
	public	function enqueue($element)
	{
		$new_node = new QueueNode($element);
		if ($this->front == null)
		{
			//When first node of queue
			$this->front = $new_node;
		}
		else
		{
			//Add node at last position
			$this->tail->next = $new_node;
		}
		$this->tail = $new_node;
	}
	//Delete first node of queue
	public	function dequeue()
	{
		if ($this->front != null)
		{
			if ($this->tail == $this->front)
			{
				$this->tail = null;
				$this->front = null;
			}
			else
			{
				$this->front = $this->front->next;
			}
		}
	}
	public	function is_empty()
	{
		if ($this->front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	public	function peek()
	{
		if ($this->is_empty() == false)
		{
			return $this->front->element;
		}
		else
		{
			return null;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	public $root;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	public	function inorder($node)
	{
		if ($node != null)
		{
			$this->inorder($node->left);
			echo "  ". $node->data;
			$this->inorder($node->right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	public	function isCompleteTree()
	{
		// Assume that initial tree is complete tree
		$status = true;
		$node = $this->root;
		if ($node != null)
		{
			// This is used to track missing child nodes
			$tracker = 0;
			// Create a queue
			$q = new MyQueue();
			// Add first node of tree
			$q->enqueue($node);
			// Execute loop until queue is not empty
			while ($node != null)
			{
				if ($status == true)
				{
					if ($node->left != null && $node->right != null)
					{
						if ($tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							$status = false;
						}
						else
						{
							// When both child exist
							$q->enqueue($node->left);
							$q->enqueue($node->right);
						}
					}
					else if ($node->left != null || $node->right != null)
					{
						// When one child exists
						$tracker++;
						if ($tracker == 1)
						{
							if ($node->right != null)
							{
								// Because left subtree are empty
								$status = false;
							}
							else
							{
								// Allow first time left subtree
								$q->enqueue($node->left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							$status = false;
						}
					}
					else
					{
						// Get a leaf node
						$tracker = 1;
					}
				}
				// Remove a queue element
				$q->dequeue();
				// Get front element of queue
				$node = $q->peek();
			}
			// Display tree elements
			$this->inorder($this->root);
			if ($status == true)
			{
				echo "\n Complete Binary Tree\n";
			}
			else
			{
				echo "\n Not a Complete Binary Tree\n";
			}
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	                  1
	                /   \
	               2     3
	             /   \     
	            4     5  
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	$tree->root = new TreeNode(1);
	$tree->root->left = new TreeNode(2);
	$tree->root->right = new TreeNode(3);
	$tree->root->left->left = new TreeNode(4);
	$tree->root->left->right = new TreeNode(5);
	$tree->root->left->left->left = new TreeNode(6);
	$tree->root->left->left->right = new TreeNode(7);
	$tree->root->left->right->left = new TreeNode(8);
	$tree->root->left->right->right = new TreeNode(9);
	// Check
	$tree->isCompleteTree();
	$tree->root->right->left = new TreeNode(-1);
	$tree->root->right->right = new TreeNode(-2);
	/*
	        After add new nodes : -1,-2
	        -----------------
	                   1
	                  /  \ 
	                 /    \  
	                /      \
	               2        3
	             /   \     / \  
	            4     5  -1  -2
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	*/
	$tree->isCompleteTree();
}
main();

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree
/*
    Node Js Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QueueNode
{
	constructor(element)
	{
		this.element = element;
		this.next = null;
	}
}
//Define custom queue class
class MyQueue
{
	constructor()
	{
		this.front = null;
		this.tail = null;
	}
	//Add a new node at last of queue
	enqueue(element)
	{
		var new_node = new QueueNode(element);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	dequeue()
	{
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	is_empty()
	{
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	peek()
	{
		if (this.is_empty() == false)
		{
			return this.front.element;
		}
		else
		{
			return null;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	inorder(node)
	{
		if (node != null)
		{
			this.inorder(node.left);
			process.stdout.write("  " + node.data);
			this.inorder(node.right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	isCompleteTree()
	{
		// Assume that initial tree is complete tree
		var status = true;
		var node = this.root;
		if (node != null)
		{
			// This is used to track missing child nodes
			var tracker = 0;
			// Create a queue
			var q = new MyQueue();
			// Add first node of tree
			q.enqueue(node);
			// Execute loop until queue is not empty
			while (node != null)
			{
				if (status == true)
				{
					if (node.left != null && node.right != null)
					{
						if (tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							status = false;
						}
						else
						{
							// When both child exist
							q.enqueue(node.left);
							q.enqueue(node.right);
						}
					}
					else if (node.left != null || node.right != null)
					{
						// When one child exists
						tracker++;
						if (tracker == 1)
						{
							if (node.right != null)
							{
								// Because left subtree are empty
								status = false;
							}
							else
							{
								// Allow first time left subtree
								q.enqueue(node.left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							status = false;
						}
					}
					else
					{
						// Get a leaf node
						tracker = 1;
					}
				}
				// Remove a queue element
				q.dequeue();
				// Get front element of queue
				node = q.peek();
			}
			// Display tree elements
			this.inorder(this.root);
			if (status == true)
			{
				process.stdout.write("\n Complete Binary Tree\n");
			}
			else
			{
				process.stdout.write("\n Not a Complete Binary Tree\n");
			}
		}
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	                  1
	                /   \
	               2     3
	             /   \     
	            4     5  
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(2);
	tree.root.right = new TreeNode(3);
	tree.root.left.left = new TreeNode(4);
	tree.root.left.right = new TreeNode(5);
	tree.root.left.left.left = new TreeNode(6);
	tree.root.left.left.right = new TreeNode(7);
	tree.root.left.right.left = new TreeNode(8);
	tree.root.left.right.right = new TreeNode(9);
	// Check
	tree.isCompleteTree();
	tree.root.right.left = new TreeNode(-1);
	tree.root.right.right = new TreeNode(-2);
	/*
	        After add new nodes : -1,-2
	        -----------------
	                   1
	                  /  \ 
	                 /    \  
	                /      \
	               2        3
	             /   \     / \  
	            4     5  -1  -2
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	tree.isCompleteTree();
}
main();

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree
#     Python 3 Program 
#     Check whether a given binary tree is complete or not

#  Binary Tree node
class TreeNode :
	
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

#  Queue Node
class QueueNode :
	
	def __init__(self, element) :
		self.element = element
		self.next = None
	

# Define custom queue class
class MyQueue :
	
	def __init__(self) :
		self.front = None
		self.tail = None
	
	# Add a new node at last of queue
	def enqueue(self, element) :
		new_node = QueueNode(element)
		if (self.front == None) :
			# When first node of queue
			self.front = new_node
		else :
			# Add node at last position
			self.tail.next = new_node
		
		self.tail = new_node
	
	# Delete first node of queue
	def dequeue(self) :
		if (self.front != None) :
			if (self.tail == self.front) :
				self.tail = None
				self.front = None
			else :
				self.front = self.front.next
			
		
	
	def is_empty(self) :
		if (self.front == None) :
			return True
		else :
			return False
		
	
	def peek(self) :
		if (self.is_empty() == False) :
			return self.front.element
		else :
			return None
		
	

#  Define Binary Tree
class BinaryTree :
	
	def __init__(self) :
		#  Set root of tree
		self.root = None
	
	def inorder(self, node) :
		if (node != None) :
			self.inorder(node.left)
			print("  ", node.data, end = "")
			self.inorder(node.right)
		
	
	#  Determine whether given binary tree is complete binary tree or not
	def isCompleteTree(self) :
		#  Assume that initial tree is complete tree
		status = True
		node = self.root
		if (node != None) :
			#  This is used to track missing child nodes
			tracker = 0
			#  Create a queue
			q = MyQueue()
			#  Add first node of tree
			q.enqueue(node)
			#  Execute loop until queue is not empty
			while (node != None) :
				if (status == True) :
					if (node.left != None and node.right != None) :
						if (tracker > 0) :
							#  When already missing one child or
							#  We already reached a leaf node
							status = False
						else :
							#  When both child exist
							q.enqueue(node.left)
							q.enqueue(node.right)
						
					
					elif(node.left != None or node.right != None) :
						#  When one child exists
						tracker += 1
						if (tracker == 1) :
							if (node.right != None) :
								#  Because left subtree are empty
								status = False
							else :
								#  Allow first time left subtree
								q.enqueue(node.left)
							
						else :
							#  When more than one child nodes are missing
							status = False
						
					else :
						#  Get a leaf node
						tracker = 1
					
				
				#  Remove a queue element
				q.dequeue()
				#  Get front element of queue
				node = q.peek()
			
			#  Display tree elements
			self.inorder(self.root)
			if (status == True) :
				print("\n Complete Binary Tree")
			else :
				print("\n Not a Complete Binary Tree")
			
		
	

def main() :
	tree = BinaryTree()
	# 
	#                   1
	#                 /   \
	#                2     3
	#              /   \     
	#             4     5  
	#            / \   / \
	#           6   7 8   9
	#       
	#         -----------------------
	#             Binary Tree
	#         -----------------------
	#         
	
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(2)
	tree.root.right = TreeNode(3)
	tree.root.left.left = TreeNode(4)
	tree.root.left.right = TreeNode(5)
	tree.root.left.left.left = TreeNode(6)
	tree.root.left.left.right = TreeNode(7)
	tree.root.left.right.left = TreeNode(8)
	tree.root.left.right.right = TreeNode(9)
	#  Check
	tree.isCompleteTree()
	tree.root.right.left = TreeNode(-1)
	tree.root.right.right = TreeNode(-2)
	# 
	#         After add new nodes : -1,-2
	#         -----------------
	#                    1
	#                   /  \ 
	#                  /    \  
	#                 /      \
	#                2        3
	#              /   \     / \  
	#             4     5  -1  -2
	#            / \   / \
	#           6   7 8   9
	#       
	#         -----------------------
	#             Binary Tree
	#         -----------------------
	#         
	
	tree.isCompleteTree()

if __name__ == "__main__": main()

Output

   6   4   7   2   8   5   9   1   3
 Not a Complete Binary Tree
   6   4   7   2   8   5   9   1   -1   3   -2
 Complete Binary Tree
#  Ruby Program 
#  Check whether a given binary tree is complete or not

#  Binary Tree node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

#  Queue Node
class QueueNode  
	# Define the accessor and reader of class QueueNode  
	attr_reader :element, :next
	attr_accessor :element, :next
 
	
	def initialize(element) 
		self.element = element
		self.next = nil
	end

end

# Define custom queue class
class MyQueue  
	# Define the accessor and reader of class MyQueue  
	attr_reader :front, :tail
	attr_accessor :front, :tail
 
	
	def initialize() 
		self.front = nil
		self.tail = nil
	end

	# Add a new node at last of queue
	def enqueue(element) 
		new_node = QueueNode.new(element)
		if (self.front == nil) 
			# When first node of queue
			self.front = new_node
		else 
			# Add node at last position
			self.tail.next = new_node
		end

		self.tail = new_node
	end

	# Delete first node of queue
	def dequeue() 
		if (self.front != nil) 
			if (self.tail == self.front) 
				self.tail = nil
				self.front = nil
			else 
				self.front = self.front.next
			end

		end

	end

	def is_empty() 
		if (self.front == nil) 
			return true
		else 
			return false
		end

	end

	def peek() 
		if (self.is_empty() == false) 
			return self.front.element
		else 
			return nil
		end

	end

end

#  Define Binary Tree
class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
 
	
	def initialize() 
		#  Set root of tree
		self.root = nil
	end

	def inorder(node) 
		if (node != nil) 
			self.inorder(node.left)
			print("  ", node.data)
			self.inorder(node.right)
		end

	end

	#  Determine whether given binary tree is complete binary tree or not
	def isCompleteTree() 
		#  Assume that initial tree is complete tree
		status = true
		node = self.root
		if (node != nil) 
			#  This is used to track missing child nodes
			tracker = 0
			#  Create a queue
			q = MyQueue.new()
			#  Add first node of tree
			q.enqueue(node)
			#  Execute loop until queue is not empty
			while (node != nil) 
				if (status == true) 
					if (node.left != nil && node.right != nil) 
						if (tracker > 0) 
							#  When already missing one child or
							#  We already reached a leaf node
							status = false
						else 
							#  When both child exist
							q.enqueue(node.left)
							q.enqueue(node.right)
						end

					elsif(node.left != nil || node.right != nil) 
						#  When one child exists
						tracker += 1
						if (tracker == 1) 
							if (node.right != nil) 
								#  Because left subtree are empty
								status = false
							else 
								#  Allow first time left subtree
								q.enqueue(node.left)
							end

						else 
							#  When more than one child nodes are missing
							status = false
						end

					else 
						#  Get a leaf node
						tracker = 1
					end

				end

				#  Remove a queue element
				q.dequeue()
				#  Get front element of queue
				node = q.peek()
			end

			#  Display tree elements
			self.inorder(self.root)
			if (status == true) 
				print("\n Complete Binary Tree\n")
			else 
				print("\n Not a Complete Binary Tree\n")
			end

		end

	end

end

def main() 
	tree = BinaryTree.new()
	# 
	#                   1
	#                 /   \
	#                2     3
	#              /   \     
	#             4     5  
	#            / \   / \
	#           6   7 8   9
	#       
	#         -----------------------
	#             Binary Tree
	#         -----------------------
	#         
	
	tree.root = TreeNode.new(1)
	tree.root.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(3)
	tree.root.left.left = TreeNode.new(4)
	tree.root.left.right = TreeNode.new(5)
	tree.root.left.left.left = TreeNode.new(6)
	tree.root.left.left.right = TreeNode.new(7)
	tree.root.left.right.left = TreeNode.new(8)
	tree.root.left.right.right = TreeNode.new(9)
	#  Check
	tree.isCompleteTree()
	tree.root.right.left = TreeNode.new(-1)
	tree.root.right.right = TreeNode.new(-2)
	# 
	#         After add new nodes : -1,-2
	#         -----------------
	#                    1
	#                   /  \ 
	#                  /    \  
	#                 /      \
	#                2        3
	#              /   \     / \  
	#             4     5  -1  -2
	#            / \   / \
	#           6   7 8   9
	#       
	#         -----------------------
	#             Binary Tree
	#         -----------------------
	#         
	
	tree.isCompleteTree()
end

main()

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree
/*
    Scala Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Queue Node
class QueueNode(var element: TreeNode , var next: QueueNode)
{
	def this(element: TreeNode)
	{
		this(element, null);
	}
}
//Define custom queue class
class MyQueue(var front: QueueNode , var tail: QueueNode)
{
	def this()
	{
		this(null, null);
	}
	//Add a new node at last of queue
	def enqueue(element: TreeNode): Unit = {
		var new_node: QueueNode = new QueueNode(element);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	def dequeue(): Unit = {
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	def is_empty(): Boolean = {
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	def peek(): TreeNode = {
		if (this.is_empty() == false)
		{
			return this.front.element;
		}
		else
		{
			return null;
		}
	}
}
// Define Binary Tree
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	def inorder(node: TreeNode): Unit = {
		if (node != null)
		{
			this.inorder(node.left);
			print("  " + node.data);
			this.inorder(node.right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	def isCompleteTree(): Unit = {
		// Assume that initial tree is complete tree
		var status: Boolean = true;
		var node: TreeNode = this.root;
		if (node != null)
		{
			// This is used to track missing child nodes
			var tracker: Int = 0;
			// Create a queue
			var q: MyQueue = new MyQueue();
			// Add first node of tree
			q.enqueue(node);
			// Execute loop until queue is not empty
			while (node != null)
			{
				if (status == true)
				{
					if (node.left != null && node.right != null)
					{
						if (tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							status = false;
						}
						else
						{
							// When both child exist
							q.enqueue(node.left);
							q.enqueue(node.right);
						}
					}
					else if (node.left != null || node.right != null)
					{
						// When one child exists
						tracker += 1;
						if (tracker == 1)
						{
							if (node.right != null)
							{
								// Because left subtree are empty
								status = false;
							}
							else
							{
								// Allow first time left subtree
								q.enqueue(node.left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							status = false;
						}
					}
					else
					{
						// Get a leaf node
						tracker = 1;
					}
				}
				// Remove a queue element
				q.dequeue();
				// Get front element of queue
				node = q.peek();
			}
			// Display tree elements
			this.inorder(this.root);
			if (status == true)
			{
				print("\n Complete Binary Tree\n");
			}
			else
			{
				print("\n Not a Complete Binary Tree\n");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		                  1
		                /   \
		               2     3
		             /   \     
		            4     5  
		           / \   / \
		          6   7 8   9
		      
		        -----------------------
		            Binary Tree
		        -----------------------
		        
		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.left.left = new TreeNode(6);
		tree.root.left.left.right = new TreeNode(7);
		tree.root.left.right.left = new TreeNode(8);
		tree.root.left.right.right = new TreeNode(9);
		// Check
		tree.isCompleteTree();
		tree.root.right.left = new TreeNode(-1);
		tree.root.right.right = new TreeNode(-2);
		/*
		        After add new nodes : -1,-2
		        -----------------
		                   1
		                  /  \ 
		                 /    \  
		                /      \
		               2        3
		             /   \     / \  
		            4     5  -1  -2
		           / \   / \
		          6   7 8   9
		      
		        -----------------------
		            Binary Tree
		        -----------------------
		        
		*/
		tree.isCompleteTree();
	}
}

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree
/*
    Swift 4 Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
// Queue Node
class QueueNode
{
	var element: TreeNode? ;
	var next: QueueNode? ;
	init(_ element: TreeNode? )
	{
		self.element = element;
		self.next = nil;
	}
}
//Define custom queue class
class MyQueue
{
	var front: QueueNode? ;
	var tail: QueueNode? ;
	init()
	{
		self.front = nil;
		self.tail = nil;
	}
	//Add a new node at last of queue
	func enqueue(_ element: TreeNode? )
	{
		let new_node: QueueNode? = QueueNode(element);
		if (self.front == nil)
		{
			//When first node of queue
			self.front = new_node;
		}
		else
		{
			//Add node at last position
			self.tail!.next = new_node;
		}
		self.tail = new_node;
	}
	//Delete first node of queue
	func dequeue()
	{
		if (self.front  != nil)
		{
			if (self.tail === self.front)
			{
				self.tail = nil;
				self.front = nil;
			}
			else
			{
				self.front = self.front!.next;
			}
		}
	}
	func is_empty()->Bool
	{
		if (self.front == nil)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	func peek()->TreeNode?
	{
		if (self.is_empty() == false)
		{
			return self.front!.element;
		}
		else
		{
			return nil;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	func inorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.inorder(node!.left);
			print("  ", node!.data, terminator: "");
			self.inorder(node!.right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	func isCompleteTree()
	{
		// Assume that initial tree is complete tree
		var status: Bool = true;
		var node: TreeNode? = self.root;
		if (node  != nil)
		{
			// This is used to track missing child nodes
			var tracker: Int = 0;
			// Create a queue
			let q: MyQueue = MyQueue();
			// Add first node of tree
			q.enqueue(node);
			// Execute loop until queue is not empty
			while (node  != nil)
			{
				if (status == true)
				{
					if (node!.left  != nil && node!.right  != nil)
					{
						if (tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							status = false;
						}
						else
						{
							// When both child exist
							q.enqueue(node!.left);
							q.enqueue(node!.right);
						}
					}
					else if (node!.left  != nil || node!.right  != nil)
					{
						// When one child exists
						tracker += 1;
						if (tracker == 1)
						{
							if (node!.right  != nil)
							{
								// Because left subtree are empty
								status = false;
							}
							else
							{
								// Allow first time left subtree
								q.enqueue(node!.left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							status = false;
						}
					}
					else
					{
						// Get a leaf node
						tracker = 1;
					}
				}
				// Remove a queue element
				q.dequeue();
				// Get front element of queue
				node = q.peek();
			}
			// Display tree elements
			self.inorder(self.root);
			if (status == true)
			{
				print("\n Complete Binary Tree");
			}
			else
			{
				print("\n Not a Complete Binary Tree");
			}
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	                  1
	                /   \
	               2     3
	             /   \     
	            4     5  
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	tree.root = TreeNode(1);
	tree.root!.left = TreeNode(2);
	tree.root!.right = TreeNode(3);
	tree.root!.left!.left = TreeNode(4);
	tree.root!.left!.right = TreeNode(5);
	tree.root!.left!.left!.left = TreeNode(6);
	tree.root!.left!.left!.right = TreeNode(7);
	tree.root!.left!.right!.left = TreeNode(8);
	tree.root!.left!.right!.right = TreeNode(9);
	// Check
	tree.isCompleteTree();
	tree.root!.right!.left = TreeNode(-1);
	tree.root!.right!.right = TreeNode(-2);
	/*
	        After add new nodes : -1,-2
	        -----------------
	                   1
	                  /  \ 
	                 /    \  
	                /      \
	               2        3
	             /   \     / \  
	            4     5  -1  -2
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	tree.isCompleteTree();
}
main();

Output

   6   4   7   2   8   5   9   1   3
 Not a Complete Binary Tree
   6   4   7   2   8   5   9   1   -1   3   -2
 Complete Binary Tree
/*
    Kotlin Program 
    Check whether a given binary tree is complete or not
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QueueNode
{
	var element: TreeNode ? ;
	var next: QueueNode ? ;
	constructor(element: TreeNode ? )
	{
		this.element = element;
		this.next = null;
	}
}
//Define custom queue class
class MyQueue
{
	var front: QueueNode ? ;
	var tail: QueueNode ? ;
	constructor()
	{
		this.front = null;
		this.tail = null;
	}
	//Add a new node at last of queue
	fun enqueue(element: TreeNode ? ): Unit
	{
		var new_node: QueueNode = QueueNode(element);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail?.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	fun dequeue(): Unit
	{
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front?.next;
			}
		}
	}
	fun is_empty(): Boolean
	{
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	fun peek(): TreeNode ?
	{
		if (this.is_empty() == false)
		{
			return this.front!!.element;
		}
		else
		{
			return null;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	fun inorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			this.inorder(node.left);
			print("  " + node.data);
			this.inorder(node.right);
		}
	}
	// Determine whether given binary tree is complete binary tree or not
	fun isCompleteTree(): Unit
	{
		// Assume that initial tree is complete tree
		var status: Boolean = true;
		var node: TreeNode ? = this.root;
		if (node != null)
		{
			// This is used to track missing child nodes
			var tracker: Int = 0;
			// Create a queue
			var q: MyQueue = MyQueue();
			// Add first node of tree
			q.enqueue(node);
			// Execute loop until queue is not empty
			while (node != null)
			{
				if (status == true)
				{
					if (node.left != null && node.right != null)
					{
						if (tracker > 0)
						{
							// When already missing one child or
							// We already reached a leaf node
							status = false;
						}
						else
						{
							// When both child exist
							q.enqueue(node.left);
							q.enqueue(node.right);
						}
					}
					else if (node.left != null || node.right != null)
					{
						// When one child exists
						tracker += 1;
						if (tracker == 1)
						{
							if (node.right != null)
							{
								// Because left subtree are empty
								status = false;
							}
							else
							{
								// Allow first time left subtree
								q.enqueue(node.left);
							}
						}
						else
						{
							// When more than one child nodes are missing
							status = false;
						}
					}
					else
					{
						// Get a leaf node
						tracker = 1;
					}
				}
				// Remove a queue element
				q.dequeue();
				// Get front element of queue
				node = q.peek();
			}
			// Display tree elements
			this.inorder(this.root);
			if (status == true)
			{
				print("\n Complete Binary Tree\n");
			}
			else
			{
				print("\n Not a Complete Binary Tree\n");
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var tree: BinaryTree = BinaryTree();
	/*
	                  1
	                /   \
	               2     3
	             /   \     
	            4     5  
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------
	        
	*/
	tree.root = TreeNode(1);
	tree.root?.left = TreeNode(2);
	tree.root?.right = TreeNode(3);
	tree.root?.left?.left = TreeNode(4);
	tree.root?.left?.right = TreeNode(5);
	tree.root?.left?.left?.left = TreeNode(6);
	tree.root?.left?.left?.right = TreeNode(7);
	tree.root?.left?.right?.left = TreeNode(8);
	tree.root?.left?.right?.right = TreeNode(9);
	// Check
	tree.isCompleteTree();
	tree.root?.right?.left = TreeNode(-1);
	tree.root?.right?.right = TreeNode(-2);
	/*
	        After add new nodes : -1,-2
	        -----------------
	                   1
	                  /  \ 
	                 /    \  
	                /      \
	               2        3
	             /   \     / \  
	            4     5  -1  -2
	           / \   / \
	          6   7 8   9
	      
	        -----------------------
	            Binary Tree
	        -----------------------    
	*/
	tree.isCompleteTree();
}

Output

  6  4  7  2  8  5  9  1  3
 Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
 Complete Binary Tree

Output Explanation

The code implements the algorithm and checks whether the given binary tree is complete or not. It constructs the binary tree, performs the check, and displays the tree elements along with the result of the check.

Time Complexity

The time complexity of this algorithm depends on the number of nodes in the binary tree. If there are N nodes in the tree, the time complexity is O(N) as each node is processed once during the level-order traversal. The space complexity is also O(N) due to the queue used for traversal.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment