Can you please let me know if I my answer is correct. Thank you 2) Let T be a bi
ID: 3825477 • Letter: C
Question
Can you please let me know if I my answer is correct. Thank you
2) 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 descendants in v’s left subtree differ from the number of descendants 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.
// v.roman is false when v is not roman and all its descendants are roman, true otherwise
romanNode(v):
if v->left == NULL and v->right == NULL:
v.numDescendants = 1
v.roman = true // v is a roman node
return (v.numDescendants, v.roman)
else
if v->left != NULL:
(a, b)=romanNode(v->left)
else:
(a, b)=(0, true);
if v.right!=null:
(a, b)=romanNode(v->right);
else:
(a, b)=(0, true);
if (|x1-x2|<=5 and y==1 and y2==1 )
v.roman=true;
else
v.roman=false;
v.numDescendants= a+b+1;
return (v.numDescendants, v.roman);
Endif
Explanation / Answer
For each node v, we introduce a variable roman. If v is not a Roman node and all of v’s descendants are Roman nodes, v.roman is set 0. Otherwise, it is set to 1.
Algorithm
romanNode(v) {
if v.left=null and v.right=null // v has no child { v.succ=1; // v.succ stores the number of descendants of v, including v itself v.roman=1;
return (v.succ, v.roman);
}
else
{
if v.left !=null (x1, y1)=romanNode(v.leftchild);
else (x1, y1)=(0, 1); if v.right!=null (x2, y2)=romanNode(v.rightchild);
else (x2, y2)=(0, 1);
if (|x1-x2|<=5 and y1=1 and y2=1 )
v.roman=1; else
v.roman=0;
v.succ= x1+x2+1;
return (v.succ, v.roman);
}
}