gistfile1.txt

// This function checks if the binary tree is complete or not
bool BinaryTree::isCompleteUtil(Node *root, int index, int size) {
    // An empty tree is complete
    if (!root) return true;
    
    // If index assigned to current node is more than
    // number of nodes in tree, then tree is not complete
    if (index >= size) return false;
    
    // Recur for left and right subtrees
    return isCompleteUtil(root->left, 2*index + 1, size) &&
            isCompleteUtil(root->right, 2*index + 2, size);
}

// Check if tree is complete
bool BinaryTree::isComplete(Node *root) {
    return isCompleteUtil(root, 0, size(root));
}

// Check if tree is complete
bool BinaryTree::isCompleteIterative(Node *root) {
    // Base case
    if (!root) return true;
    
    queue<Node *> q;
    q.push(root);
    
    // Create a flag variable which will be set true when a non full node is seen
    bool flag = false;
    
    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        
        // Check if left child is present
        if (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 tree
            if (flag) return false;
            q.push(node->left);
        } else {
            // This is a non full node
            flag = true;
        }
        
        // Check if right child is present
        if (node->right) {
            if (flag) return false;
            q.push(node->right);
        } else {
            flag = true;
        }
    }
    return true;
}