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

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 vs left subtree differ from the number of descendants in vs 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 vs 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

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!