Reference no: EM132098922

Can you please let me know if the answer is correct.

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