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