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
Get step-by-step solutions from verified subject matter experts
