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.
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)
}
The simplest procedure is:
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.
//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));
}
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);
}
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:
Advantage: entire tree may not be traversed
Overhead: maintaining flag entries
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);
}
You can also solve this problem by using level order traversal. The procedure is as follows:
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";
}
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/
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;
}
}
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.
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.
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.
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);
}
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 ;
}
