Let T be a binary tree with n nodes. Define a Roman node to be a node v in T, su
ID: 3782707 • Letter: L
Question
Let T be a binary tree with n nodes. Define a Roman node to be a node v in T, such that the number of nodes in v's left subtree differ from the number of nodes in v's right subtree by at most 5. Describe a linear-time method for finding each node v of T, such that v is not a Roman node, but all of v's descendants are Roman nodes. Counting leaves Describe a recursive method that counts the number of leaves in a given binary tree. Describe a non-recursive method that counts the number of leaves in a given binary tree.Explanation / Answer
a)
For each Node, add property "roman". If it is roman Node, set value to 1 else set to 0.
If any Node is not roman, then desscendant nodes are roman nodes.
Algorithm checkIsRomanNode(vertex)
{
if vertex.left=null and vertex.right=null // if it is a child Node
{
vertex.succ=1; // storing number of descendants
itself
vertex.roman=1;
return (vertex.succ, vertex.roman);
}
else
{
if vertex.left !=null
(x1, y1)=checkIsRomanNode(vertex.leftchild);
else
(x1, y1)=(0, 1);
if vertex.right!=null
(x2, y2)=checkIsRomanNode(vertex.rightchild);
else
(x2, y2)=(0, 1);
if (|x1-x2|<=5 and y1=1 and y2=1 )
vertex.roman=1;
else
vertex.roman=0;
vertex.succ= x1+x2+1;
return (vertex.succ, vertex.roman);
}
}
------------------------------------------------------------------------------------------------------------------------------------------
b)
/* Recursive method to count number of leaves */
int countLeafCount(struct Node* Node)
{
if(Node == NULL)
return 0;
if(Node->left == NULL && Node->right==NULL)
return 1;
else
return countLeafCount(Node->left)+countLeafCount(Node->right);
}
------------------------------------------------------------------------------------------------------------------------------------------
/* Non-Recursive method to count number of leaves */
int countLeafCount(NODE *ptr)
{
NODE *stackNodes[40];
int top=-1;
int count=0;
if(ptr==NULL)
return 0;
stackNodes[++top]=ptr;
while(top!=-1)
{
ptr=stackNodes[top--];
while(ptr!=NULL)
{
if(ptr->leftchild==NULL && ptr->rightchild==NULL)
count++;
if(ptr->rightchild!=NULL)
stackNodes[++top]=ptr->rightchild;
ptr=ptr->leftchild;
}
}
return count;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.