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
- Implement the
isCompleteTree
function that takes the binary tree as input. - Create a queue using the
makeQueue
function. - Enqueue the root node into the queue.
- Initialize a flag
missingNodesAllowed
as true. This flag keeps track of whether missing nodes are allowed in the current level. - Initialize the status of the tree as true. This status will be updated to false if any violation is encountered.
- Start a loop that continues while the queue is not empty.
- Inside the loop, dequeue the front node from the queue.
- Check if the left child of the current node exists. If it does, enqueue it into the queue.
- Check if the right child of the current node exists. If it does, enqueue it into the queue.
- Update the
missingNodesAllowed
flag based on the existence of children. - 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. - 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. - Repeat this process for all nodes in the current level.
- After the loop ends, use an inorder traversal to display the tree elements.
- 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.
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