Computer Science HW Help

[chris53825]

Hey everyone,

I've been pulling my hair out with this one, but maybe someone can be my angel!
Alright here's the question:

"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 descendents in v’s left subtree differ from the number of descendents in v’s right subtree by at most 5. Describe a linear-time method/function for finding each node v of T, such that v is not a Roman node, but all of v’s descendents are Roman nodes."
a pseudo code solution is required

So basically from what I understand, a Roman node is a node where # of children in left or right differ by <= 5. I am to create a function which find each node that is not a Roman node, but all of its descendants are (inherently).

My most sensible approach to this is to start off at the root node and traverse it all the way down one side, arbitrarily the right side. once it hits it's last node, traverse the left branch of every node as it backtracks and keep a count somehow of each node in the subtree.

I suppose I'm most confused on how to find the number of differing descendants per node in O(n) time.

Maybe I'm totally over complicating this. Can someone please enlighten me? Thank you so much in advance

[Duoas]

Think of it recursively.

[chris53825]

Will that give a solution in linear time ?

[Duoas]

As long as you don't examine sub-nodes more than once, yes.

[chris53825]

Alright, So I've come to the conclusion this requires some sort of inorder traversal

inorder(node)
if node.left ≠ null then inorder(node.left)
do something here
if node.right ≠ null then inorder(node.right)

I'm just not sure how to keep track of each side's children.. any ideas?