0

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

2
Contributors
4
Replies
5
Views
9 Years
Discussion Span
Last Post by chris53825
0

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?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.