Developer Forum

I am trying to determine if an n-ary tree is balanced or not, I have
been stuck trying several approaches and am getting nowhere. My new
thought is that i will have to step through each node of the tree, and
compare the lengths of the roots of the children, making sure there is
not a difference greater than one in the values for all of the
children. Am i thinking in the right direction, or is there a simpler
solution?

thanks,
kim
--
comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

Yes, a depth first traversal that sounds like the easiest way to me.

All nodes at depth 'd' must have no children and all nodes at depth
d-2 (or less) must have n children,

Traverse the tree and report the depth of the deepest node and the
depth of the shallowest node not having n children,

If the difference is more than 1 the tree is unbalanced,

this is easily written as a recursive function but may perform better
(by some small, fixed, multiple) as a stack-based iterative function.
--
comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

cgirl < XXXX@XXXXX.COM > writes:

Your question is off-topic for this newsgroup, but yes, this is the
definition of a balanced tree, and no, there is no other way to do it.
What you call "the lengths of the roots of the children" is usually
called the height of the node.

You should get these: http://www.yqcomputer.com/

DES
--
Dag-Erling Smrgrav - XXXX@XXXXX.COM
--
comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

One more soln.
N ary tree
L=get no of nodes in tree.
H=get max height level of tree.
if(floor(log baseN(L))==H-1) true
else false
This is for height balanced tree


--
comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.