Check whether a given Binary Tree is Complete or not | GeeksforGeeks
Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.
The method 2 of level order traversal post can be easily modified to check whether a tree is Complete or not. To understand the approach, let us first define a term ‘Full Node’. A node is ‘Full Node’ if both left and right children are not empty (or not NULL).
The approach is to do a level order traversal starting from root. In the traversal, once a node is found which is NOT a Full Node, all the following nodes must be leaf nodes.
Also, one more thing needs to be checked to handle the below case: If a node has empty left child, then the right child must be empty.
Check whether a binary tree is a complete tree or not | Set 2 (Recursive Solution)
Read full article from Check whether a given Binary Tree is Complete or not | GeeksforGeeks
Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. See following examples.
The approach is to do a level order traversal starting from root. In the traversal, once a node is found which is NOT a Full Node, all the following nodes must be leaf nodes.
Also, one more thing needs to be checked to handle the below case: If a node has empty left child, then the right child must be empty.
bool isCompleteBT(struct node* root){ // Base Case: An empty tree is complete Binary Tree if (root == NULL) return true; // Create an empty queue int rear, front; struct node **queue = createQueue(&front, &rear); // Create a flag variable which will be set true // when a non full node is seen bool flag = false; // Do level order traversal using queue. enQueue(queue, &rear, root); while(!isQueueEmpty(&front, &rear)) { struct node *temp_node = deQueue(queue, &front); /* Ceck if left child is present*/ if(temp_node->left) { // If we have seen a non full node, and we see a node // with non-empty left child, then the given tree is not // a complete Binary Tree if (flag == true) return false; enQueue(queue, &rear, temp_node->left); // Enqueue Left Child } else // If this a non-full node, set the flag as true flag = true; /* Ceck if right child is present*/ if(temp_node->right) { // If we have seen a non full node, and we see a node // with non-empty left child, then the given tree is not // a complete Binary Tree if(flag == true) return false; enQueue(queue, &rear, temp_node->right); // Enqueue Right Child } else // If this a non-full node, set the flag as true flag = true; } // If we reach here, then the tree is complete Bianry Tree return true;}Check whether a binary tree is a complete tree or not | Set 2 (Recursive Solution)
- Calculate the number of nodes (count) in the binary tree.
- Start recursion of the binary tree from the root node of the binary tree with index (i) being set as 0 and the number of nodes in the binary (count).
- If the current node under examination is NULL, then the tree is a complete binary tree. Return true.
- If index (i) of the current node is greater than or equal to the number of nodes in the binary tree (count) i.e. (i>= count), then the tree is not a complete binary. Return false.
- Recursively check the left and right sub-trees of the binary tree for same condition. For the left sub-tree use the index as (2*i + 1) while for the right sub-tree use the index as (2*i + 2).
/* This function counts the number of nodes in a binary tree */unsigned int countNodes(struct Node* root){ if (root == NULL) return (0); return (1 + countNodes(root->left) + countNodes(root->right));}/* This function checks if the binary tree is complete or not */bool isComplete (struct Node* root, unsigned int index, unsigned int number_nodes){ // An empty tree is complete if (root == NULL) return (true); // If index assigned to current node is more than // number of nodes in tree, then tree is not complete if (index >= number_nodes) return (false); // Recur for left and right subtrees return (isComplete(root->left, 2*index + 1, number_nodes) && isComplete(root->right, 2*index + 2, number_nodes));} unsigned int node_count = countNodes(root); unsigned int index = 0; if (isComplete(root, index, node_count)) printf("The Binary Tree is complete\n"); else printf("The Binary Tree is not complete\n");