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();
}

Answer 2

Consider doing as follows:

int is_full_tree(node *root, int depth){
if (root->left != NULL && root->right != NULL){
    int left = is_full_tree(root->left, depth+1);
    int right = is_full_tree(root->right, depth+1);
    if (left == right && left != -1)
        return left; // or right doesn't matter
    else
        return -1;
}
else if (root->left == NULL && root->right == NULL)
    return depth;
return -1;
}

The functions get's called recursively until it reaches the leaves where the depth of each leave is returned, then the depths are compared and if they are equal (the recursion reached the same depth in every subtree) the value of the depth is returned. Hence the function returns -1 if the tree is not full, and some value representing the depth if it is full.

The first call should be is_full_tree(root,0)

EDIT:

To check if a tree is a complete binary tree (all levels have all nodes except maybe the last one and all nodes are pushed to the left), hence it will be complete if the depth of the leaves are equal, or the left is by 1 bigger then the right one (the opposite does not hold), hence we modify as follows:

std::pair<int,int> is_complete_tree(node *root, int depth){
    if (root->left != NULL && root->left != NULL){
        std::pair<int,int> left = is_complete_tree(root->left, depth+1);
        std::pair<int,int> right = is_complete_tree(root->right, depth+1);
        if (left.first != -1 && left.second != -1 && right.first != -1 && right.second != -1)
            if (left.first == right.first && left.first == left.second)
                return right; //assuming right.first - right.second == 1 or 0
            else if (left.first == left.second && right.first == right.second && left.first - right.first == 1)
                return std::pair<int,int>(left.first,right.first); 
            else if (left.first - left.second == 1 && left.second == right.first  && right.first == right.second)
                return left;
            else
                return std::pair<int,int>(-1,-1);
        else
            return std::pair<int,int>(-1,-1);
    }

    else if (root->left != NULL && root->right == NULL)
        if (root->left->right == NULL && root->left->left == NULL)
            return std::pair<int,int>(depth+1,depth); // the root->left is NULL terminated
        else 
            return std::pair<int,int>(-1,-1); // the .left is not NULL terminated

    else if (root->left == NULL && root->right == NULL) //condition for leaves
        return std::pair<int,int>(depth,depth);
    return std::pair<int,int>(-1,-1); // if .left == NULL and .right != NULL
    }

You can also go generalizing the 2nd algo to do both things. You can add a flag which will go as parameter by reference and will get modified only if the first else if evaluates to true which will mean that there is a parent which has his left depth longer by 1 then his right depth. Hence the algo will return again the depth of the tree if it is a complete tree and -1 otherwise.

The idea of the 2nd algo is the same as of the first one. The difference is that we have to keep track of both "max" and "min" depths (there is not such thing as max and min depth but that is the intuition behind the idea, the "min depth" would be the depth of the deepest node that has only 1(left) child) recorded in any subtree in order to be able to analyze a tree as this one for example:

         A
      /    \
    B        C
   /\        /\
 D    E    F    G
/\   /\   /\   /\
H I J     K L  M

Where we have to know what happened in the subtrees where B and C are the roots when we analyse them. So at the point when we compare B and C, B(left) will have the pair value (3,2) where the 3 stand for H, Iand J having depth of 3, and 2 for the Enode that is missing his right child. C(right) will also have the value (3,2) hence the tree is incomplete because there is a "rupture" in both subtrees, hence not all nodes are left aligned.

Answer 3

One way to do it could indeed be a level order traversal, as you suggested, implement it a as a BFS, and push to your queue pairs of (level,node). The tree is full if and only if each level except the last has double the number of nodes of the previous, or 2^level.

Have a look at the following pseudo code:

is_full_binary(root) { 
  queue q = new queue()
  q.push(pair(0,root))
  int currentNodes = 0
  int current = 0
  while q.isEmpty() == false { 
    level, node = q.pop()
    q.push(pair(level+1, node.left)) // make sure such exist before...
    q.push(pair(level+1, node.right)) //same here
    if level == current
         currentNodes++
    else {
         if currentNodes != 2^current
              return false
         currentNodes = 0
         current = level
    }
  }
return true
}

The above pseudo code checks for each level if it has exactly 2^level nodes, and return true of it does, and false otherwise - meaning it checks if the tree is full.

Checking if it is not full, but complete requires a bit more work for the last level - and is left for you, the concept of it will be very similar.

Answer 4

Here is the simple solution to problem using space efficient DFS algorithm as opposed to BFS ones:-

1. Use DFS on tree
2. Record the min depth & max depth among all paths from root to null
3. if max depth == min depth then it is full binary tree
4. if max depth == min depth + 1 && flag < 2 where denotes change in depth of null from left then complete binary tree
5. else not both.

Psuedo code:-

void caldepths(Node p,int depth) {

   if(p==null) {

      if(max!=-infinity && max<depth) {

         flag = 2;
      }

      if(max<depth)
          max = depth

      if(min>depth)
          min = depth



      if(max!=-infinity && depth<max && flag==0) {
           flag = 1; 
      }
      if(depth==max && flag==1) {

            flag = 2;   
      }

   }

  else {

      caldepths(p.left,depth+1)
      caldepths(p.right,depth+1)
  }

}

void caltype(root) {

   max = -infinity
   min = infinity
   flag = 0;
   caldepths(root,0)
   if(max == min)
      print("full binary tree")
   if(max == min+1 && flag<2)
      print("complete binary tree")
   else print("Not both")
}      

Answer 5

Code below for the "is complete" - with a comment showing the half-line to remove to test for a perfect binary tree (i.e. one with all leaves at the same depth). This is compilable code, with 3 test cases at the end.

The algorithmic bit is depths(), reproduced here for discussion: with extra comments inline and below (and without cout trace).

LR depths(Node& n)
{
    // NULL/NULL is handled correctly below anyway, but nice not to have to think about it
    if (n.l == NULL && n.r == NULL) return LR();

    // get the depths of the child nodes... LR() is (0,0)
    LR l12 = n.l ? ++depths(*n.l) : LR();
    LR r12 = n.r ? ++depths(*n.r) : LR();

    // >= ensures left-hand branches are as deep or deeper, i.e. left packing
    if (l12.l >= l12.r && l12.r >= r12.l && r12.l >= r12.r &&
        // also check the leftmost-to-rightmost depth range is 0 (full tree below)
        // or 1 (perfect tree)
        (l12.l == r12.r || l12.l == 1 + r12.r))
        return LR(l12.l, r12.r);

    throw false; // children can't be part of a full or complete tree
}

To explain the concept - consider any tree (or part thereof) that looks like this, where child / grandchild nodes might or might not exist:

     Node
     /   \
  *l       r 
  / \     / \
*l1 l2   r1 r2

The algorithm generates a "depth" number for how far down the l1, l2, r1 and r2 paths you can go. Say only the nodes with *s actually exist - i.e. l and l1 exist but l2 doesn't - then l1's depth would be 2, but l2's would be 1. r doesn't exist at all, then r1 and r2 would be 0.

The algorithm then observes: if l1, l2, r1 and r2 are equal, then the tree is "perfect". If they differ, then it may still be a complete tree, but the depths must decrease by 1 somewhere: e.g. if the grandchildren are leaf nodes, then (2, 2, 2, 1) or (2, 2, 1, 1) or (2, 1, 1, 1) or (1, 1, 1, 0) or (1, 1, 0, 0) or (1, 0, 0, 0). The easiest way to test for that is to check that l1 >= l2 >= r1 >= r2 && l1 == r2 + 1 - i.e. there's never an increase in depth, and the depth of the ends are only 1 apart.

Finally, the algorithm recurses deeply into the tree until it's dealing with a node with at least 1 child, then does the validation, then the lower and higher ends of the spanned range (which are at most 1 apart) are passed up for consideration of the up-to-four child paths from the parent node.

This consideration of four child paths at a time is a bit unusual and complicated, but it allows us to easily detect a situation where across four nodes the depth differs by more than 1.

If I'd only considered 2 nodes at a time, then a tree with two steps couldn't be detected without an extra has-already-stepped or max-depth-seen variable... but as Vikram's answer proves - using such a variable is easier over-all.

Full code:

#include <iostream>
#include <algorithm>
#include <string>
#include <cassert>

struct Node
{
    std::string n;
    Node* l;
    Node* r;
    Node(const char n[]) : n(n), l(0), r(0) { }
    Node(const char n[], Node& l, Node& r) : n(n), l(&l), r(&r) { }
    Node(const char n[], Node& l, int) : n(n), l(&l), r(0) { }
    Node(const char n[], int, Node& r) : n(n), l(0), r(&r) { }
};

struct LR
{
    int l, r;
    LR(int l, int r) : l(l), r(r) { }
    LR() : l(0), r(0) { }
    LR& operator++() { ++l; ++r; return *this; }
    bool operator==(const LR& rhs) const { return l == rhs.l && r == rhs.r; }
};

std::ostream& operator<<(std::ostream& os, const LR& lr)
{ return os << lr.l << ',' << lr.r; }

LR depths(Node& n)
{
    if (n.l == NULL && n.r == NULL) return LR();
    LR l12 = n.l ? ++depths(*n.l) : LR();
    LR r12 = n.r ? ++depths(*n.r) : LR();
    if (l12.l >= l12.r && l12.r >= r12.l && r12.l >= r12.r &&
        (l12.l == r12.r || l12.l == 1 + r12.r))
    {
        LR result = LR(l12.l, r12.r);
                std::cout << "depths(" << n.n << "), l12 " << l12 << ", r12 " << r12
                  << ", result " << result << '\n';
        return result;
    }
    std::cerr << "!complete @ " << n.n << ' ' << l12 << ' ' << r12 << '\n';
    throw false;
}

bool is_complete_tree(Node& root)
{
    try
    {
        depths(root);
        return true;
    }
    catch (...)
    {
        return false;
    }
}

int main()
{
    {
        std::cerr << "left node no children, right node two children\n";
        Node rl("rl"), rr("rr"), r("r", rl, rr), l("l"), root("root", l, r);
        assert(!is_complete_tree(root));
    }

    {
        std::cerr << "left node two children, right node no children\n";
        Node ll("ll"), lr("lr"), l("l", ll, lr), r("r"), root("root", l, r);
        assert(is_complete_tree(root));
    }

    {
        std::cerr << "left node two children, right node two children\n";
        Node ll("ll"), lr("lr"), l("l", ll, lr);
        Node rl("rl"), rr("rr"), r("r", rl, rr);
        Node root("root", l, r);
        assert(is_complete_tree(root));
    }

    std::cerr << ">>> test 3-level tree with 1 missing leaf at 3rd level\n";

    {
        std::cerr << "left node left child, right node two children\n";
        Node ll("ll"), l("l", ll, 0);
        Node rl("rl"), rr("rr"), r("r", rl, rr);
        Node root("root", l, r);
        assert(!is_complete_tree(root));
    }

    {
        std::cerr << "left node right child, right node two children\n";
        Node           lr("lr"), l("l", 0, lr);
        Node rl("rl"), rr("rr"), r("r", rl, rr);
        Node root("root", l, r);
        assert(!is_complete_tree(root));
    }

    {
        std::cerr << "left node two children, right node left child\n";
        Node ll("ll"), lr("lr"), l("l", ll, lr);
        Node rl("rl"),           r("r", rl, 0 );
        Node root("root", l, r);
        assert(is_complete_tree(root));
    }

    {
        std::cerr << "left node two children, right node right child\n";
        Node ll("ll"), lr("lr"), l("l", ll, lr);
        Node           rr("rr"), r("r", 0,  rr);
        Node root("root", l, r);
        assert(!is_complete_tree(root));
    }
}