Gmail Calendar Documents Reader Web more »
Recently Visited Groups | Help | Sign in
Google Groups Home
Algorithm Geeks
Home
+ new post
Pages
Files
About this group
Join this group
Determining if an n-ary tree is balanced or not.
Options
There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic.
There was an error processing your request. Please try again.
flag
   4 messages - Collapse all  -  Translate all to Translated (View all originals)
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
cgirl  
View profile  
 More options Jun 25, 10:46 pm
From: cgirl <dmitche...@twmi.rr.com>
Date: Thu, 25 Jun 2009 19:46:36 -0700 (PDT)
Local: Thurs, Jun 25 2009 10:46 pm
Subject: Determining if an n-ary tree is balanced or not.
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author
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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
sharad kumar  
View profile  
 More options Jun 26, 12:14 am
From: sharad kumar <aryansmit3...@gmail.com>
Date: Fri, 26 Jun 2009 09:44:54 +0530
Local: Fri, Jun 26 2009 12:14 am
Subject: Re: [algogeeks] Determining if an n-ary tree is balanced or not.
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author

ok if its not balanced how do u balance it??


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
cgirl  
View profile  
 More options Jun 26, 12:22 am
From: cgirl <dmitche...@twmi.rr.com>
Date: Thu, 25 Jun 2009 21:22:23 -0700 (PDT)
Local: Fri, Jun 26 2009 12:22 am
Subject: Re: Determining if an n-ary tree is balanced or not.
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author
i only need to determine if at each node the depths of
the subtrees rooted at its children are the same or differ at most by
1.

On Jun 26, 12:14 am, sharad kumar <aryansmit3...@gmail.com> wrote:


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
tec  
View profile  
 More options Jun 26, 1:19 am
From: tec <technic....@gmail.com>
Date: Fri, 26 Jun 2009 13:19:06 +0800
Local: Fri, Jun 26 2009 1:19 am
Subject: Re: [algogeeks] Determining if an n-ary tree is balanced or not.
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author
I think you are in the right direction. Using DFS, the complexity is
O(m+n) = O(n). No better complexity I think.

2009/6/26 cgirl <dmitche...@twmi.rr.com>:

> 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

--
__________________________________________________

    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
End of messages
« Back to Discussions « Newer topic     Older topic »

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2009 Google