To check wether it's a complete binary tree or fully binary tree or neither of the two

Question

I am new with the concept if binary trees. I have been stuck at a question for many days. It is to find if a given tree is a binary tree or a fully binary tree or neither of the two.

I have thought of many algorithm but none of them fulfill each and every case. I tried google but there was no proper solution.

I thought of using Level Order Traversal Technique but couldn't come up with how to know thier levels after all the nodes have been inserted in the queue.

For the Fully Binary tree I tried counting if the degree of all the nodes are 0 or 2 but then if the tree has some intermediate node with degree this logic is also wrong.

I have made a tree using a linked list, The basic - Left Child, Right Child Relationship way.

For the fully binary tree I do a inorder traverl and checked the degree if 0 or 2, but it's wrong cause if there's a node at some earlier level with degree 0 then also then output comes true.

For the complete binary tree i couldn't come up with anything proper.

Thank You.

And I am using C++, so if the logic uses pointers then it's alright.

Answer 1

Checking for Full is easy:
By the definition here. http://courses.cs.vt.edu/cs3114/Summer11/Notes/T03a.BinaryTreeTheorems.pdf

The tree is full if all nodes have either 0 or two children.

bool full(Node* tree)
{
    // Empty tree is full so return true.
    // This also makes the recursive call easier.
    if (tree == NULL)
    {   return true;
    }

    // count the number of children
    int count = (tree->left == NULL?0:1) + (tree->right == NULL?0:1);

    // We are good if this node has 0 or 2 and full returns true for each child.
    // Don't need to check for left/right being NULL as the test on entry will catch
    // NULL and return true.
    return count != 1 && full(tree->left) && full(tree->right);
}

Complete is a little harder.
But the easiest way seems to be a breadth first (left to right) traversal of the tree. At each node push both left and right onto the list be traversed (even if they are NULL). After you hit the first NULL there should only be NULL objects left to find. If you find a non NULL object after this it is not a complete tree.

bool complete(Node* tree)
{
    // The breadth first list of nodes.
    std::list<Node*>  list;
    list.push_back(tree);   // add the root as a starting point.

    // Do a breadth first traversal.
    while(!list.empty())
    {
        Node* next = list.front();
        list.pop_front();

        if (next == NULL)
        {   break;
        }

        list.push_back(next->left);
        list.push_back(next->right);
    }

    // At this point there should only be NULL values left in the list.
    // If this is not true then we have failed.

    // Written in C++11 here.
    // But you should be able to traverse the list and look for any non NULL values.
    return std::find_if(list.begin(), list.end(), [](Node* e){return e != NULL;}) != list.end();
}