The task is to check whether a given binary tree is a complete binary tree or not.

• A complete binary tree is a binary tree where every level, except possibly the last, is completely filled.

• All nodes in...read more

Step1. First I provided the solution , that just do the inorder traversal and check whether the output is sorted or not
Step2. Interviewer asked to do without inorder traversal. So implemented with re...read more

The idea is to observe the fact that in the Level Order Traversal of any Complete Binary Tree, all the Non-Null nodes come in succession, and all the Null nodes come after them. Using this observation, we can check whether the given binary tree is a complete binary tree. The level order traversal can be done with an approach that is similar to Breadth First Search (BFS). While traversing the Tree in level order, we will maintain a flag variable to check whether we have found a Null node till now. If, at any time, we find a Non-Null node after a Null node, then the given binary tree will not be a Complete Binary Tree, otherwise, it will always be a complete binary tree.

Steps:

1. Let q be a queue that will be used for the Level-order Traversal.
2. Insert root of the tree into the q. 
3. Let isNullFound be a flag variable that checks whether we have encountered any Null node till now. Initialize it as 0.
4. While q is not empty,
   • Remove a node from q, let currNode be the removed node.
   • If currNode is a Null Node, then
     • Set isNullFound as 1, as we have found a Null Node.
   • Otherwise, if isNullFound is 1, then return 0. As we have already found a Null Node earlier, and now we found a Non-Null node. Hence, the given Binary Tree cannot be a Complete Binary Tree.
   • Otherwise, add both the childs of currNode to the queue q.
5. We will return 1 if we have not returned any value till now. As we have traversed the Binary Tree and we were not able to find a Non-Null node after a Null Node. Hence, the given Tree will be a Complete Binary Tree.

O(N), where N is the number of nodes in the given binary tree.

The number of elements in the queue will be equal to the maximum number of nodes at any level of the Binary Tree, which can be N+1 in the worst case. Hence, the overall Space Complexity is O(N).

O(N), where N is the number of nodes in the given binary tree. 

As each node of the Binary Tree is added and removed from the Binary Tree only once. Hence, the overall Time Complexity is O(N).

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of nodes in the Binary Tree.

'''

from collections import deque



def isCompleteBinaryTree(root):

    

    # Initializing the queue and inserting the root into the queue

    q = deque()



    q.append(root)



    isNullFound = 0

    while (len(q) > 0):



        # Removing a node from the queue

        currNode = q.popleft()



        # Checking if the removed node is a Null node

        if (currNode == None):

            isNullFound = 1

        else:



            # Checking if we have already found any Null node

            if (isNullFound):

                return 0



            # Adding both the childs of current node to the queue

            q.append(currNode.left)

            q.append(currNode.right)



    return 1

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of nodes in the Binary Tree.

*/



import java.util.LinkedList;

import java.util.Queue;



public class Solution 

{

    public static int isCompleteBinaryTree(TreeNode root) 

    {

        // Initializing the queue and inserting the root into the queue

        Queue> q = new LinkedList();

        q.add(root);



        int isNullFound = 0;



        while (q.size() != 0)

        {

            // Removing a node from the queue

            TreeNode currNode = q.peek();

            q.poll();



            // Checking if the removed node is a Null node

            if (currNode == null)

            {

                isNullFound = 1;

            }

            else

            {

                // Checking if we have already found any Null node

                if (isNullFound == 1)

                {

                    return 0;

                }



                // Adding both the childs of current node to the queue

                q.add(currNode.left);

                q.add(currNode.right);

            }

        }



        return 1;

    }

}

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of nodes in the Binary Tree.

*/



#include 



int isCompleteBinaryTree(TreeNode *root)

{

    // Initializing the queue and inserting the root into the queue

    queue *> q;

    q.push(root);



    int isNullFound = 0;



    while (q.size())

    {

        // Removing a node from the queue

        TreeNode *currNode = q.front();

        q.pop();



        // Checking if the removed node is a Null node

        if (currNode == NULL)

        {

            isNullFound = 1;

        }

        else

        {

            // Checking if we have already found any Null node

            if (isNullFound)

            {

                return 0;

            }



            // Adding both the childs of current node to the queue

            q.push(currNode->left);

            q.push(currNode->right);

        }

    }



    return 1;

}

The idea is to first number the nodes of the binary tree in the order that they will be visited if we traverse the Binary Tree level by level. Note that we will start numbering the nodes from 1, and we will number the Tree assuming that the Tree is a complete Binary Tree. Now consider any complete Binary Tree, and use this to observe the fact that the maximum number assigned to a Non-Null node of the Binary Tree will always be equal to the number of nodes in the Binary Tree. Using this observation, we can traverse the Binary Tree recursively similar to doing a Depth First Search (DFS) and count the number of nodes in the tree and the maximum index number assigned to a node of the tree. If both the obtained values are equal, then the given Binary Tree is a complete binary tree, otherwise, it is not. Note that if a particular node has been assigned the number i, then its left children will always be assigned the number 2*i, and the right children will be assigned 2*i+1.

Steps: 

1. Let maxIndex, nodes be the two global variables that store the maximum index of a node we have found and the number of nodes that we have found respectively. Initialize both the variables as 0.
2. Let dfs be a recursive function that takes a currRoot node and currIndex as parameters, and is used to recursively traverse the subtree rooted at currRoot. Here currRoot denotes the current node, and currIndex denotes the index being assigned to the current node.
   • If currRoot is a Non-Null node, then
     • Increase the variable nodes by 1.
     • Set maxIndex as the maximum value among maxIndex among maxIndex and currIndex. 
     • Call dfs for the left child of currNode taking 2*currIndex as the new currIndex.
     • Call dfs for the right child of currNode taking 2*currIndex + 1as the new currIndex.
3. If maxIndex equals Nodes, then return 1. Otherwise, return 0.

O(N), where N is the number of nodes in the given binary tree. 

In the worst case, when the given tree is a skewed tree. The recursion stack depth will be N. Hence, the overall Space Complexity is O(N).

O(N), where N is the number of nodes in the given binary tree. 

As we are visiting each node of the binary tree only once. Hence, the overall Time Complexity is O(N).

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of nodes in the Binary Tree.

'''



# Recursive function to traverse the subtree rooted at currRoot

def dfs(currRoot, currIndex, maxIndex, nodes):

    

    # Checking if the current node is a Non-Null node

    if (currRoot):



        # Updating the variables

        nodes[0] += 1

        maxIndex[0] = max(maxIndex[0], currIndex)



        # Recursively calling for the left subtree and the right subtree

        dfs(currRoot.left, 2 * currIndex, maxIndex, nodes)

        dfs(currRoot.right, 2 * currIndex + 1, maxIndex, nodes)





def isCompleteBinaryTree(root):

    

    maxIndex, nodes = [0], [0]



    # Calling the DFS function for the root node

    dfs(root, 1, maxIndex, nodes)



    # Checking if the maximum index found equals the number of Non-Null nodes visited

    if (maxIndex == nodes):

        return 1



    return 0

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of nodes in the Binary Tree.

*/



// Recursive function to traverse the subtree rooted at currRoot

void dfs(TreeNode *currRoot, int currIndex, int &maxIndex, int &nodes)

{

    // Checking if the current node is a Non-Null node

    if (currRoot)

    {

        // Updating the variables

        nodes++;

        maxIndex = max(maxIndex, currIndex);



        // Recursively calling for the left subtree and the right subtree

        dfs(currRoot->left, 2*currIndex, maxIndex, nodes);

        dfs(currRoot->right, 2*currIndex + 1, maxIndex, nodes);

    }

}



int isCompleteBinaryTree(TreeNode *root)

{

    int maxIndex = 0, nodes = 0;



    // Calling the DFS function for the root node

    dfs(root, 1, maxIndex, nodes);



    // Checking if the maximum index found equals the number of Non-Null nodes visited

    if (maxIndex == nodes)

    {

        return 1;

    }

    return 0;

}

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of nodes in the Binary Tree.

*/



public class Solution 

{   

    public static int maxIndex , nodes;

    

    // Recursive function to traverse the subtree rooted at currRoot

    public static void dfs(TreeNode currRoot, int currIndex)

    {

        // Checking if the current node is a Non-Null node

        if (currRoot != null)

        {

            // Updating the variables

            nodes++;

            maxIndex = Math.max(maxIndex, currIndex);



            // Recursively calling for the left subtree and the right subtree

            dfs(currRoot.left, 2 * currIndex);

            dfs(currRoot.right, 2 * currIndex + 1);

        }

    }



    public static int isCompleteBinaryTree(TreeNode root) 

    {

        maxIndex = 0; nodes = 0;



        // Calling the DFS function for the root node

        dfs(root, 1);



        // Checking if the maximum index found equals the number of Non-Null nodes visited

        if (maxIndex == nodes) 

        {

            return 1;

        }

        return 0;

    }

}