• Status: Solved
• Priority: Medium
• Security: Public
• Views: 716

# 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
• 10
• 4
• 3
• +1
3 Solutions

Commented:
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

Commented:
#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

Author 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

Author 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.

- #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

Commented:
#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

Author 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

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?

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

Author 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

Commented:
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

Commented:
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

Author Commented:
Hi All,

I'll be back later.

Thank you.
0

Author Commented:
Hi TeamSrv,

I can not get your point.

Would you please use excel sample  ?

Thank you.
0

Author Commented:
Hi Tommy,

I can not get your point.

Would you please use excel sample  ?

Thank you.
0

Commented:
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

Author Commented:
Hi Tommy,

Yes, get it.

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

Thank you.
0

Commented:
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

Author Commented:
Great.

Thank you very much to both of you.
0

Author Commented:
Thank you very much to all of you.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.