[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 711
  • Last Modified:

BINARY TREE

Hi All,

I want to know math of :

1. How many many tree (3 nodes) for a full node level of a tree?.
    For example : 3 level contains 7 nodes have 3 tree which are :
    1. 1-2-3
    2. 2-4-5
    3. 3-6-7

2. How many nodes of each node of a full node level of a tree ?
    For example : 3 level contains 7 nodes have 3 tree which are :
    1. Node 1 has 6 nodes = 2-4-5-3-6-7
    2. Node 2 has 2 node = 4-5
    3. Node 3 has 2 node = 6-7

3. How to find level of a node of a full node level of a tree ?
    For example : 3 level contains 7 nodes have 3 tree which are :
    1. Node 1 = Level 1
    2. Node 2 and 3 = Level 2
    3. Node 4,5,6,7 = Level 3
    etc

Thank you.    
0
emi_sastra
Asked:
emi_sastra
  • 10
  • 4
  • 3
  • +1
3 Solutions
 
TommySzalapskiCommented:
There's one important thing to notice that basically answers all three of your questions.
At each level, the number of nodes doubles.
So you have 1 then 2 then 4 then 8 then 16 then 32 etc.

The math would be: at level n there are (2^(n-1)) nodes (remember that 2^0 = 1)

So the number of nodes of the whole tree is 2^n - 1
For #2 notice that each node in the tree with all the nodes under it is the same as a tree.
So node 3 is the root of a tree with 2 levels.
0
 
SuperdaveCommented:
#1:  If you're asking about specifically about  three-node subtrees, it would be equivalent to asking how many nodes it has excluding leaf nodes, or in other words how many nodes in an n-1 level tree.  You can think of it as counting the root nodes of the subtrees.

#2:  I don't understand the question.  It makes my head spin.  It looks like maybe you mean the size of the subtree - 1, which would be the total number of levels minus the level of the node (see #3) and take two to that power and subtract 1.

#3:  The way you are numbering them, the level of Node #n would be [lg(n-1)]+1.
[ ] meaning floor and lg meaning base-two-logarithm.
0
 
emi_sastraAuthor Commented:
Hi Tommy,

- The math would be: at level n there are (2^(n-1)) nodes (remember that 2^0 = 1)
I already understand this, this is not in my question.

- For #2 notice that each node in the tree with all the nodes under it is the same as a tree.
- So node 3 is the root of a tree with 2 levels.
I don't get this.

Thank you.
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
emi_sastraAuthor Commented:
Hi Superdave,

- #1:  If you're asking about specifically about  three-node subtrees, it would be equivalent to asking how many nodes it has excluding leaf nodes, or in other words how many nodes in an n-1 level tree.  You can think of it as counting the root nodes of the subtrees.
Please provide its math.

- #2:  I don't understand the question.  It makes my head spin.  It looks like maybe you mean the size of the subtree - 1, which would be the total number of levels minus the level of the node (see #3) and take two to that power and subtract 1.
I have no idea convert it into excel math and vb code.

#3:  The way you are numbering them, the level of Node #n would be [lg(n-1)]+1.
[ ] meaning floor and lg meaning base-two-logarithm.
I have no idea convert it into excel math and vb code.

Thank you.
0
 
SuperdaveCommented:
#1: That would be 2^(n-1)-1.
#2: You have no idea of what, what your question means?
#3: I have no idea either.  I don't see how that would make it any more understandable.
Maybe just replace [] with INT() like INT(LG(n-1))+1.  Not sure if LG is a BASIC function either.  If not try INT(LN(n-1)/LN(2))+1.  If that doesn't do it try LOG instead of LN.


0
 
emi_sastraAuthor Commented:
- #1: That would be 2^(n-1)-1.
Ok.

- #2: You have no idea of what, what your question means?
1. Level 1 has 6 Members (2,3,4,5,6,7) from Level 2 (2) and Level 3 (4)
2. Level 2 hase 2 Members (4,5) from Level 3.
3. Level 3 hase 2 Members (6,7)from Level 3.

 - #3: I have no idea either.  I don't see how that would make it any more understandable.
Maybe just replace [] with INT() like INT(LG(n-1))+1.  Not sure if LG is a BASIC function either.  If not try INT(LN(n-1)/LN(2))+1.  If that doesn't do it try LOG instead of LN.
Still can not do it.

Thank you.


0
 
SuperdaveCommented:
#2: I still don't get the question.  Why is one half of level 3 associated with level 2 and the other half with level 3?

#3: Maybe try adding VB or Excel to the zones to find somebody who knows about those.
0
 
emi_sastraAuthor Commented:
#2: I still don't get the question.  Why is one half of level 3 associated with level 2 and the other half with level 3?
Count All Member below a node, Node 1 have  6 members.

#3: Maybe try adding VB or Excel to the zones to find somebody who knows about those.
Ok.

Thank you.
0
 
TeamSrvCommented:
Hi Emi,
Floor[(Log(x)/Log(2)] + 1 will give you the level of the x node.
*Floor just means round down.

If you are trying to convert this into VB code, Math.Floor and Math.Log are what you are looking for.
If you are trying to convert this into Excel code use:
=FLOOR(LOG(A1,2),1)+1
Where A1 holds the number of the node you are looking for.

Hope that helps.
0
 
TommySzalapskiCommented:
For part 2 I believe the question is just asking how many nodes are under node x.

Notice that if you look at how many nodes are under node x, you are looking at a binary tree. If this doesn't make sense, draw a binary tree and then circle a node in the middle and all the nodes under it. Notice how they form a tree.

So if the original tree has a depth of D and the node is at level L then the subtree has depth (D-L+1) and the total nodes under x is (2^(D-L+1)  -2)
-2 because the original formula has a -1 and you are not counting node x so you need another -1.
0
 
emi_sastraAuthor Commented:
Hi All,

I'll be back later.

Thank you.
0
 
emi_sastraAuthor Commented:
Hi TeamSrv,

I can not get your point.

Would you please use excel sample  ?

Thank you.
0
 
emi_sastraAuthor Commented:
Hi Tommy,

I can not get your point.

Would you please use excel sample  ?

Thank you.
0
 
TommySzalapskiCommented:
The question is how many nodes are under node x right?
So get the level of the node (from your part 3)
Then it's just 2^(TotalTreeHeight - Level_of_x + 1)  - 2
In Excel VBA you write it the same way.
In Excel formulas say the height of the tree is in G1 and the level of X is in G2 you would use power(2, G1-G2+1)-2
0
 
emi_sastraAuthor Commented:
Hi Tommy,

Yes, get it.

How about question 3, given node number and find its level ?

Thank you.
0
 
TommySzalapskiCommented:
The answer is in http:#a37018985
You take the log base 2 of the node's number and round down. Then add 1 to the result.
If you've never used the log function in math, then just take TeamSrv's word for it that the formulas he posted work, because they are the only good way to do it.
0
 
emi_sastraAuthor Commented:
Great.

Thank you very much to both of you.
0
 
emi_sastraAuthor Commented:
Thank you very much to all of you.
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 10
  • 4
  • 3
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now