Given Bst Is Complete Tree Or Not?

[leeza]

there is a binary search tree given in which user performs some insertions
now we have to check whether this bst ic a complete tree or not?


complete tree is a tree in which there is no empty node in the tree.


now inorder to chk that is there any empty node before the last node?

after some study i only got one condition that

if no. of nodes in left subtree are less than that of right subtree
then tree is incomplete.
for this we count all the nodes(left and right) in the root's left subtree and right sub tree.
i also thought to introduce height factor but i was very much confused becuz there still remain such conditions where it also failed .

plz help me .
to solve this problem.
efficiency is not the issue here.
so an inefficint code is also acceptible.
thanks

[mehdi62b]

well,it depends on the structure you are using for your tree,anyway I suppose it's a linked list[C#] public bool IsComplete(NodeT first)
{
if(first.right!=null && first.left==null)
return false;
if(first.left!=null && first.right==null)
{
NodeT node=first.left;
if(node.left!=null || node.right !=null)
return false;
return true;
}
if(first.left==null && first.right==null)
{
return true;
}
if(first.left!=null && first.right!=null)
{
bool b=IsComplete(first.left);
bool c=true;
NodeT lchild=first.left;
NodeT rchild=first.right;
bool rcondition=rchild.right==null;
NodeT llchild=lchild.left;
NodeT lrchild=lchild.right;
bool lcondition=
(llchild!=null && lrchild.right!=null);
if(rcondition && lcondition)
{
if(llchild.left!=null || llchild.right!=null
|| lrchild.left!=null || lrchild.right!=null)
c=false;

}
else{c=IsComplete(first.right);}
return (b && c);
}
return true;
}which would take O(n).
Edit:
&& means and.
|| means or.

[jeffrey@toad.net]

Hi Leeza,

mehdi62b code looks correct (I don't do C#). I would have recursively solved it also.

If this is a real world app (as opposed to an Algorithm Analysis homework problem), you might also perform a quick and dirty test before the process begins at the root:

make sure node (non-NULL) count is equal to 2^h - 1, where h is equal to the height of the tree.

Jeff

[leeza]

thanks Mr. Mehdi for ur reply.

[leeza]

hi ,

I have a problem in understanding this block of code(sent by Mr. Mehdi)
/*
bool c=true;
NodeT lchild=first.left;
NodeT rchild=first.right;
bool rcondition=rchild.right==null;
NodeT llchild=lchild.left;
NodeT lrchild=lchild.right;
bool lcondition=
(llchild!=null && lrchild.right!=null);
if(rcondition && lcondition)
{
if(llchild.left!=null || llchild.right!=null
|| lrchild.left!=null || lrchild.right!=null)
c=false;

}
else{c=IsComplete(first.right);}
return (b && c);
***********************/

1)bool lcondition= (llchild!=null && lrchild.right!=null);
why don't u use " lrchild!=null" instead of " lrchild.right!=null"



the code given is working ok for left subtree but


for inputs like 7,5,9,4,8 (7 is ROOT)
remember it is binary search tree's insertion
here it gives TRUE but it is not a complete tree.


I didn't understand clearly the purpose of right and left condition .I think its for right subtree
But for inputs like


7,5,9,8,4,6,3 (7 is ROOT)

is also incomplete tree and it gives it as TRUE.
plz reply me soon.


THANKS

[mehdi62b]

for inputs like 7,5,9,4,8 (7 is ROOT)
remember it is binary search tree's insertion
here it gives TRUE but it is not a complete tree.yes,you are ight,it didn't check that,I can not fix that now,but there is also another solution!
you can change the structure of the linked list to an array then simply you can check that array for a complete tree
I have written some code which works(I use a dynamic array or ArrayList)surelly its idea is correct //*ar* would have an array for the linked list
private void complete(NodeT f,int n,ArrayList ar)
{
if(f!=null)
{
ar[n]=f;
if (f.left!=null && f.right!=null)
{
object[] temp=new object[n+1];
ar.AddRange(temp);
ar[2*n]=f.left;
ar[2*n+1]=f.right;
complete(f.left,2*n,ar);
complete(f.right,2*n+1,ar);
}
else
{
if(f.left!=null && f.right==null)
{
object[] temp=new object[n];
ar.AddRange(temp);
ar[2*n]=f.left;
complete(f.left,2*n,ar);
}
else
{
if(f.left==null && f.right!=null)
{
object[] temp=new object[n+1];
ar.AddRange(temp);
ar[2*n+1]=f.right;
complete(f.right,2*n+1,ar);
}
}
}
}
}
private bool IsComplete(NodeT f)
{
bool result=true;
if(f!=null)
{
ArrayList ar=new ArrayList();
ar.Add(null);
ar.Add(f);
complete(f,1,ar);
//now *ar* would have an array for the linked list
int i=1;
for(int c=i;c<ar.Count && ar[c]!=null;c++,i=c){}
for(int c=i;c<ar.Count;c++)
if(ar[c]!=null)
result=false;
}
return result;
}that works,I should think on the first solution more though..