CODEWITHSUNDEEP
algorithmbinary-tree
Akshay
Akshay

Reputation:

How to determine whether a binary tree is complete?

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.

Upvotes: 7

Views: 30797

Answers (16)

Mohammad
Mohammad

Reputation: 6148

First, count the number of nodes in the binary tree. Write a recursive function. If the received node is null, it returns true. If the index of the node is greater than or equal number of nodes, the tree is not binary. If none of these two happened, check the left and right sub-trees. import java.util.LinkedList; import java.util.Queue;

public class FBCompleteTree {

    /*
    public class TreeNode {

        Integer val;
        TreeNode left;
        TreeNode right;

        TreeNode(Integer x) {
            val = x;
        }

    }
     */

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        FBCompleteTree completeTree = new FBCompleteTree();
        System.out.println(completeTree.isCompleteTree(node1));
    }

    public boolean isCompleteTree(TreeNode root) {
        int nodeCount = countNodes(root);
        // The index of the root is always zero.
        return isComplete(root, nodeCount, 0);
    }

    /**
     * Tells us if a binary tree is complete or not.
     *
     * @param node      The current node
     * @param nodeCount The node counts of the tree
     * @param index     The index of the node
     * @return If a binary tree is complete or not
     */
    private boolean isComplete(TreeNode node, int nodeCount, int index) {
    // Null is a complete binary tree
    if (node == null)
        return true;
    // In a complete binary tree, index of all the nodes should be less than nodes count.
    if (index >= nodeCount)
        return false;
    /*
    The index of the left child is 2*i+1 and the right child is 2*i+2 in a binary tree.
     */
    return isComplete(node.left, nodeCount, 2 * index + 1)
            &&
            isComplete(node.right, nodeCount, 2 * index + 2);
}

    /**
     * Counts the number of nodes.
     *
     * @param root The root of the tree
     * @return The number of nodes in the tree
     */
    private int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int counter = 0;
        while (!q.isEmpty()) {
            TreeNode currentNode = q.poll();
            counter++;
            TreeNode l = currentNode.left;
            if (l != null) {
                q.add(l);
            }
            TreeNode r = currentNode.right;
            if (r != null) {
                q.add(r);
            }
        }
        return counter;
    }

}

I hope it helps.

Upvotes: 0

clyde correa
clyde correa

Reputation: 86

bool isComplete (struct Node* root){
    if(root==NULL)
    return true;                  // Recur for left and right subtree 
    bool flag=false;
    int option1=height(root->left);
    int option2=height(root->right);
    if(option1==option2||option1==option2+1)
    flag=true;
    return flag&&isComplete(root->left)&&isComplete(root->right);
    }

please consider as a correct answer if you found useful.

Upvotes: 0

Uchiha_Sasuke
Uchiha_Sasuke

Reputation: 31

For a tree to be complete

height(left) == height(right) or height(left) == 1+height(right)

    bool isComplete (struct Node* root){
    if(root==NULL)
    return true;                  // Recur for left and right subtree 
    bool flag=false;
    int option1=height(root->left);
    int option2=height(root->right);
    if(option1==option2||option1==option2+1)
    flag=true;
    return flag&&isComplete(root->left)&&isComplete(root->right);
    }

Upvotes: 2

user417369
user417369

Reputation: 21

//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));

}

Upvotes: 2

Rgarg
Rgarg

Reputation: 506

Here is a C code for checking if the binary tree is complete:

struct node
{
    int data;
    struct node * left;
    struct node * right;
};
int flag;
int isComplete(struct node *root, int depth)
{
    int ld, rd;
    if (root==NULL) return depth;
    else
    {
        ld =  isComplete(root->left,depth+1);
        rd = isComplete(root->right, depth+1);
        if (ld==-1 || rd==-1) return -1;
        else if (ld==rd) return ld;
        else if (ld==rd-1 && flag==0)
        {
            flag=1;
            return rd;
        }
        else return -1;
    }
}

The way it works is:

  • If the depth of left subtree is same as depth of right subtree, it returns the depth up the hirearchy.

  • if the depth of left subtree is one more than the depth of right subtree, it returns depth of right subtree up the hirarchy and enables the flag.

  • If it finds that the depth of left subtree and right subtree and flag is already set, it returns -1 up the hierarchy.

  • In the end, if the function returns -1, it is not the complete subtree, else the value returned is the minimum depth of the tree.

Upvotes: 0

spiralmoon
spiralmoon

Reputation: 3272

Thanks for @Jonathan Graehl 's pseudo code. I've implemented it in Java. I've tested it against iterative version. It works like a charm!

public static boolean isCompleteBinaryTreeRec(TreeNode root){
//      Pair notComplete = new Pair(-1, false);
//      return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete);
    return isCompleteBinaryTreeSubRec(root).height != -1;
}

public static boolean isPerfectBinaryTreeRec(TreeNode root){
    return isCompleteBinaryTreeSubRec(root).isFull;
}

public static Pair isCompleteBinaryTreeSubRec(TreeNode root){
    if(root == null){
        return new Pair(0, true);
    }

    Pair left = isCompleteBinaryTreeSubRec(root.left);
    Pair right = isCompleteBinaryTreeSubRec(root.right);

    if(left.isFull && left.height==right.height){
        return new Pair(1+left.height, right.isFull);
    }

    if(right.isFull && left.height==right.height+1){
        return new Pair(1+left.height, false);
    }

    return new Pair(-1, false);
}

private static class Pair{
    int height;         
    boolean isFull;     

    public Pair(int height, boolean isFull) {
        this.height = height;
        this.isFull = isFull;
    }

    public boolean equalsTo(Pair obj){
        return this.height==obj.height && this.isFull==obj.isFull;
    }
}

Upvotes: 0

Chinmay
Chinmay

Reputation: 751

private static boolean isCompleteBinaryTree(TreeNode root) {

if (root == null) {
    return false;
} else {
    boolean completeFlag = false;
    List<TreeNode> list = new ArrayList<TreeNode>();
    list.add(root);
    while (!list.isEmpty()) {
        TreeNode element = list.remove(0);
        if (element.left != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.left);
        } else {
            completeFlag = true;
        }
        if (element.right != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.right);
        } else {
            completeFlag = true;
        }
    }
        return true;
    }
}

Reference: Check the following link for a detailed explanation http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

Upvotes: 0

Nivetha
Nivetha

Reputation: 708

You can also solve this problem by using level order traversal. The procedure is as follows:

  1. Store the data element of the nodes encountered in a vector
  2. If the node is NULL, then store a special number(INT_MIN)
  3. Keep track of the last non-null node visited - lastentry
  4. Now traverse the vector till lastentry. If you ever encounter INT_MIN, then the tree is not complete. Else it is a complete binary tree.

Here is a c++ code:

My tree node is:

struct node{
    int data;
    node *left, *right;
};

void checkcomplete(){//checks whether a tree is complete or not by performing level order traversal
    node *curr = root;
    queue<node *> Q;
    vector<int> arr;
    int lastentry = 0;
    Q.push(curr);
    int currlevel = 1, nextlevel = 0;
    while( currlevel){
        node *temp = Q.front();
        Q.pop();
        currlevel--;
        if(temp){
            arr.push_back(temp->data);
            lastentry = arr.size();
            Q.push(temp->left);
            Q.push(temp->right);
            nextlevel += 2;
        }else
            arr.push_back(INT_MIN);
        if(!currlevel){
            currlevel = nextlevel;
            nextlevel = 0;
        }
    }
    int flag = 0;
    for( int i = 0; i<lastentry && !flag; i++){
        if( arr[i] == INT_MIN){
            cout<<"Not a complete binary tree"<<endl;
            flag = 1;
        }
    }
    if( !flag )
        cout<<"Complete binary tree\n";
}

Upvotes: 0

Chen Pang
Chen Pang

Reputation: 1388

The following code simply treats every possible cases. Tree height is obtained along the way to avoid another recursion.

enum CompleteType
{
    kNotComplete = 0,
    kComplete = 1, // Complete but not full
    kFull = 2,
    kEmpty = 3
};

CompleteType isTreeComplete(Node* node, int* height)
{
    if (node == NULL)
    {
        *height = 0;
        return kEmpty;
    }

    int leftHeight, rightHeight;

    CompleteType leftCompleteType = isTreeComplete(node->left, &leftHeight);
    CompleteType rightCompleteType = isTreeComplete(node->right, &rightHeight);

    *height = max(leftHeight, rightHeight) + 1;

    // Straight forwardly treat all possible cases
    if (leftCompleteType == kComplete && 
        rightCompleteType == kEmpty &&
        leftHeight == rightHeight + 1)
        return kComplete;

    if (leftCompleteType == Full)
    {
        if (rightCompleteType == kEmpty && leftHeight == rightHeight + 1)
            return kComplete;
        if (leftHeight == rightHeight)
        {
            if (rightCompleteType == kComplete)
                return kComplete;
            if (rightCompleteType == kFull)
                return kFull;
        }
    }

    if (leftCompleteType == kEmpty && rightCompleteType == kEmpty)
        return kFull;

    return kNotComplete;
}

bool isTreeComplete(Node* node)
{
    int height;
    return (isTreeComplete(node, &height) != kNotComplete);
}

Upvotes: 0

Sandipan
Sandipan

Reputation: 1

int height (node* tree, int *max, int *min) {

  int lh = 0 , rh = 0 ;
  if ( tree == NULL )
    return 0;
  lh = height (tree->left,max,min) ;
  rh = height (tree->right,max,min) ;
  *max = ((lh>rh) ? lh : rh) + 1 ;
  *min = ((lh>rh) ? rh : lh) + 1 ;
  return *max ;
}

void isCompleteUtil (node* tree, int height, int* finish, int *complete) {
  int lh, rh ;
  if ( tree == NULL )
    return ;
  if ( height == 2 ) {
    if ( *finish ) {
      if ( !*complete )
        return;
      if ( tree->left || tree->right )
        *complete = 0 ;
      return ;
    }
    if ( tree->left == NULL && tree->right != NULL ) {
      *complete = 0 ;
      *finish = 1 ;
    }
    else if ( tree->left == NULL && tree->right == NULL )
      *finish = 1 ;
    return ;
  }
  isCompleteUtil ( tree->left, height-1, finish, complete ) ;
  isCompleteUtil ( tree->right, height-1, finish, complete ) ;
}

int isComplete (node* tree) {
  int max, min, finish=0, complete = 1 ;
  height (tree, &max, &min) ;
  if ( (max-min) >= 2 )
    return 0 ;
  isCompleteUtil (tree, max, &finish, &complete) ;
  return complete ;
}

Upvotes: -1

PSg
PSg

Reputation: 57

The simplest procedure is:

  1. Find depth of the tree (simple algorithm).
  2. Count the number of nodes in a tree (by traversing and increasing the counter by one on visiting any node).
  3. For a complete binary tree of level d number of nodes equals to pow(2,d+1)-1.

If condition satisfy tree, is complete binary tree, else not.

That's a simple algorithm and turning it into a working code shouldn't be a problem if you are good enough coder.

Upvotes: 4

user224517
user224517

Reputation: 1

There may be one possible algorithm which I feel would solve this problem. Consider the tree:

Level 0:    a  
Level 1:  b   c  
Level 2: d e f g

  • 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 exist both children set a global flag = true.
      1. Set flags for each node in the queue as true: flag[b] = flag[c] = true.
      2. Check for each entry if they have left n right child n then set the flags or reset them to false.
      3. (Dequeue) if(queue_empty())
        compare all node flags[]... if all true global_flag = true else global_flag = false.
      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

Upvotes: 0

Svante
Svante

Reputation: 51531

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.

Upvotes: 0

ejspencer
ejspencer

Reputation: 102

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

Upvotes: -1

Jonathan Graehl
Jonathan Graehl

Reputation: 9301

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

Upvotes: 5

starblue
starblue

Reputation: 56822

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)

Upvotes: 0

Related Questions