🔒 Locked

a Binary Tree problem......

Started by nabeelisnabeel Jan 31, 2006 at 11:15 PM 5 replies 800+ views

Original Post

Jan 31, 2006 at 11:15 PM

hi guys I have to write a function get_level_with_maximum_no_of_nodes(); I think the name is self-explanatory. I m using a Linked represenatation of binary tree. I guess this function has somethign to do with Level Order Printing of binary tree , which uses a queue? mm not sure, jhust a guess. any pointers fomr ur side dudes?

Endar

Jan 31, 2006 at 11:49 PM

Someone correct me if I'm wrong, but I have a feeling that the only way you'll be able to do this is traverse the whole tree and keep track of how many nodes on each level using an array or something.

eleusive

Feb 1, 2006 at 3:51 AM

You might as well just have an array representing how many nodes are at each level, and increment/decrement array whenever you insert/remove a new element onto level i. Then, you could just have a variable that contains the index of the level with the most number of nodes, and update that as you insert/remove elements.

_goat

Feb 1, 2006 at 5:34 AM

Node * getNodeWithMaximumChildren(Node * top_of_branch){	if (countNodes(top_of_branch->left_node) >= countNodes(top_of_branch->right_node))		return top_of_branch->left_node;	else		return top_of_branch->right_node;}unsigned long countNodes(Node * node){	unsigned long left_count = 0, right_count = 0;		if (node->left_node) left_count = countNodes(node->left_node);	if (node->right_node) right_count = countNodes(node->right_node);		return left_count + right_count;}

(Edit: Written because it's been a while since I wrote a recursive function)

jpetrie

Feb 1, 2006 at 11:50 AM

_goat, your countNodes fails to account for node you are currently looking at. It will always return zero.

nabeelisnabeel

Feb 1, 2006 at 7:25 PM

Thanx for all of you 4 ur help.
I will apply your code and see hat works.

discman1028

Feb 1, 2006 at 10:52 PM

Quote:
Please notice that the code above is not re-entrant (and hence e.g. not thread save). It would be better to allocate the array outside and to pass it into the function. The solution above need not be a problem but may become one in the future, so I wanted it to be mentioned so that nabeelisnabeel is aware of.

Can you elaborate on what re-entrant and not thread safe means?

(http://www.gamedev.net/community/forums/topic.asp?topic_id=372915)

Thanks.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.