How to determine whether a binary tree is complete?

Question

A complete binary tree is defined as a binary tree in which every level, except possibly the deepest, is completely filled. At deepest level, all nodes must be as far left as possible.

I'd think a simple recursive algorithm will be able to tell whether a given binary tree is complete, but I can't seem to figure it out.

Answer 1

Similar to:

height(t) = if (t==NULL) then 0 else 1+max(height(t.left),height(t.right))

You have:

perfect(t) = if (t==NULL) then 0 else { 
                  let h=perfect(t.left)
                  if (h != -1 && h==perfect(t.right)) then 1+h else -1
             }

Where perfect(t) returns -1 if the leaves aren't all at the same depth, or any node has only one child; otherwise, it returns the height.

Edit: this is for "complete" = "A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level.[1] (This is ambiguously also called a complete binary tree.)" (Wikipedia).

Here's a recursive check for: "A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.". It returns (-1,false) if the tree isn't complete, otherwise (height,full) if it is, with full==true iff it's perfect.

complete(t) = if (t==NULL) then (0,true) else { 
                  let (hl,fl)=complete(t.left)
                  let (hr,fr)=complete(t.right)                      
                  if (fl && hl==hr) then (1+h,fr)
                  else if (fr && hl==hr+1) then (1+h,false)
                  else (-1,false)
              }

Answer 2

You could combine three pieces of information from the subtrees:

• Whether the subtree is complete

• The maximal height

• The minimal height (equal to maximal height or to maximal height - 1)

Answer 3

You can tell if a given binary tree is a left-complete binary tree - better known as a binary heap by ensuring that every node with a right child also has a left child. See below

bool IsLeftComplete(tree)
{

  if (!tree.Right.IsEmpty && tree.Left.IsEmpty)
    //tree has a right child but no left child, therefore is not a heap
    return false;    

  if (tree.Right.IsEmpty && tree.Left.IsEmpty)  
    //no sub-trees, thus is leaf node. All leaves are complete
    return true;

  //this level is left complete, check levels below
  return IsLeftComplete(tree.Left) && IsLeftComplete(tree.Right);
}

Answer 4

'there may be one possible algorithm which i feel shall be solving out this problem:
consider the tree
level 0: a
level 1: b c
level 2: d e f g
d e are children of b and f g are of c (left child n right child)
* we employ breadth first traversal
* for each enqueued element in the queue we have to make three checks in order:
1. if there is a single child or no child terminate else check 2
2. if there exists both child set a global flag = true
2.1 set flags for each node in the queue as true (flag[b] = flag[c] =true
2.2 check for each entry if they have left n right child n then set the flags or reset them to false
2.3 (dequeue) if(queue_empty())
compare all node flags[]... if all true global_flag = true else global_flag= false
2.4 if global_flag = true go for proceed with next level in breadth first traversal else terminate

advantage: entire tree may not be traversed
overhead: maintaining flag entries

Answer 5

You can do it recursively by comparing the heights of each node's children. There may be at most one node where the left child has a height exactly one greater than the right child; all other nodes must be perfectly balanced.

Answer 6

//Author : Sagar T.U, PESIT //Helper function

int depth (struct tree * n) { int ld,rd;

if (n == NULL) return 0;

ld=depth(n->left); ld=depth(n->right);

if (ld>rd) return (1+ld); else return (1+rd);

}

//Core function

int isComplete (struct tree * n) { int ld,rd;

if (n == NULL) return TRUE;

ld=depth(n->left); rd=depth(n->right);

return(ld==rd && isComplete(n->left) && isComplete(n->right));

}