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.
Read full article from Check whether a given Binary Tree is Complete or not | GeeksforGeeks
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.
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;}
No comments:
Post a Comment