How to determine if a binary tree is complete?

Question

A complete binary tree is defined as a binary tree in which each level, with the possible exception of the deepest, is completely populated. At the deepest level, all nodes should be as distant as possible.

I would have thought that a simple recursive algorithm would be able to determine if a given binary tree is complete, but I cannot figure it out.

Answer 1

Similarly:

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 are not all at the same depth, or if any node has only one child; otherwise, it returns the height.

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

Here's a recursive check for: "A complete binary tree is a binary tree in which each level, with the possible exception of the last, is completely populated and all nodes as far as possible.". It returns (-1, false) if the tree is not completed, otherwise (height, full), if there is one, with the full value true, if it is 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

The simplest procedure:

• Find the depth of the tree (simple algorithm).
• Count the number of nodes in the tree (by moving and increasing the counter by one when visiting any node).
• For a complete binary tree of level d, the number of nodes is pow (2, d + 1) -1.

If the condition satisfies the tree, it is a complete binary tree, otherwise not.

That a simple algorithm and turning it into working code should not be a problem if you are a good enough encoder.

Answer 3

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

Answer 4

To make the tree 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); } 

Answer 5

You can combine three pieces of information from subtrees:

• Is the subtree full

• Maximum height

• Minimum height (equal to maximum height or maximum height - 1)

Answer 6

Perhaps there is one possible algorithm that I think will solve this problem. Consider the tree:

 Level 0: a Level 1: bc Level 2: defg 

• We use the width of the first traversal.

• For each selected item in the queue, we must do three checks in order:

  • If there is one child or no child is completed; else, check 2.
  • If both parents exist, set the global flag = true.
    • Set the flags for each node in the queue as true: flag [b] = flag [c] = true.
    • Check for each entry if they left n the right child n, then set the flags or reset to false.
    • (Dequeue) if (queue_empty ())
      compare all flags of node [] ... if all true global_flag = true else global_flag = false.
    • If global_flag = true go to continue the next level in width, the first round still completes

Advantage: whole tree cannot be traversed
Overhead: saving flag entries

Answer 7

You can do this recursively by comparing the heights of each of the node children. There can be no more than one node, where the left child has a height exactly one greater than the right child; all other nodes should be perfectly balanced.

Answer 8

The following code simply considers all possible cases. The height of the tree 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); } 

Answer 9

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

• Save the item data nodes found in the vector
• If node is NULL, keep the special number (INT_MIN)
• Keep track of the last nonblank node visited - lastentry
• Now move the vector to the end. If you ever encounter INT_MIN, then the tree is not complete. Otherwise, it is a complete binary tree.

Here is the C ++ code:

My tree node:

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

Answer 10

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

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

Answer 11

Thanks for the @Jonathan Graehl pseudo code. I implemented it in Java. I tested it against the 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; } } 

Answer 12

Here is the C code to check for binary tree completion:

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

How it works:

• If the depth of the left subtree is the same as the depth of the right subtree, it returns the depth to the hierarchy.

• if the depth of the left subtree is greater than the depth of the right subtree, it returns the depth of the right subtree up the hierarchy and turns on the flag.

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

• In the end, if the function returns -1, this is not a complete subtree, otherwise the return value will be the minimum depth of the tree.

Answer 13

 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 the answer correct if you find this helpful.

Answer 14

You can find out if a given binary tree is a left full binary tree - better known as a binary heap, ensuring that each node with the 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 15

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