M-ary Tree: Given Nodes, find leaves

[scorpius1782]

Homework Statement

(I'm struggling with trees now so I expect to have a lot more questions on here like this)

I have a 4-ary tree with 173 nodes. How many leaves do I have?

Homework Equations

The Attempt at a Solution

So I know that each node, if it is not a leaf, will have 4 nodes coming off of it (stated in problem). It seems to me that there should be a quick and simple way to do this... but I can't figure it out. Like all of these other problems I can't simply draw the trees and expect to be able to count without being 100% sure I didn't make a mistake. Or even have it drawn and turned in on time since they can be quite large...

So, I tried simple examples. Say only 2 of the first 4 shared it, then: 1+4+2*4+8*4+32*4=173. Well, I know that at height 1 there are 2 leaves. Height 2 there are no leaves.. and at height 4 they must all be leaves. Therefore, there are 2+32*4=130 leaves.

I believe I'm right but is there a simpler way to do this??

 

[Mark44]

Homework Statement

(I'm struggling with trees now so I expect to have a lot more questions on here like this)

I have a 4-ary tree with 173 nodes. How many leaves do I have?

Homework Equations

The Attempt at a Solution

So I know that each node, if it is not a leaf, will have 4 nodes coming off of it (stated in problem). It seems to me that there should be a quick and simple way to do this... but I can't figure it out. Like all of these other problems I can't simply draw the trees and expect to be able to count without being 100% sure I didn't make a mistake. Or even have it drawn and turned in on time since they can be quite large...

So, I tried simple examples. Say only 2 of the first 4 shared it, then: 1+4+2*4+8*4+32*4=173. Well, I know that at height 1 there are 2 leaves. Height 2 there are no leaves.. and at height 4 they must all be leaves. Therefore, there are 2+32*4=130 leaves.

I believe I'm right but is there a simpler way to do this??

I don't understand what you're doing, so I don't know if the number you got is correct. Counting the nodes seems more to me like adding a finite series.

Top level (root) : 1 node
2nd level: 4 nodes
3rd level: 16 nodes
4th level: 64 nodes
5th level: 256 nodes

For each node in a given level, there can be up to 4 nodes below it. At each level, the number of nodes would be four times the number of nodes in the previous level. In the top two levels there are 5 nodes in all. In the top three levels, there are 21 nodes in all. In the top four levels, there are 85 nodes in all, and so on. Since there are fewer than 1 + 4 + 16 + 64 + 256 nodes, the fifth level can't be full, so some of the nodes in the fourth level must be leaves, not nodes.

That's how I would approach it.

 

[scorpius1782]

I started the problem this way but couldn't figure out how I could simply get the number of leaves. I mean, some of the 4th level clearly have leaves but I have no idea how many. That is why I resorted to examples.

 

[Mark44]

From the root through the 4th level there are 85 nodes. How many more nodes do you need to get to a total of 173 nodes? The remainder have to be in the 5th level. Some of the nodes at the 4th level will necessarily turn out to be leaf nodes.

 

[scorpius1782]

173-85=88, so 22 nodes in level 4 have children and 44 are leaves. 44+88=132. That's too many, I think. Have I made a mistake?

 

[Mark44]

No, 22 nodes in level 4 have children (4 apiece) and 42 of the nodes in level 4 are leaves. All 88 of the level 5 nodes are leaves.

 

[scorpius1782]

No, 22 nodes in level 4 have children (4 apiece) and 46 of the nodes in level 4 are leaves. All 88 of the level 5 nodes are leaves.

But, that would make 68 nodes in level 4.

 

[Mark44]

I wrote 46, but meant 42. It was pretty late when I wrote that. It is now corrected in my earlier post.

 

[scorpius1782]

Okay, I just noticed my mistake as well. Thats what happens I write on my phone as I'm falling asleep in bed. Thanks for the help

 

[Mark44]

The answer here is less important than the technique I used, which was pretty much just counting how many nodes there were at each level, and the running totals for the levels. Since you had 173 nodes, and levels 1 through 4 accounted for a total of 85 nodes, and levels 1 through 5 could have at most 341 nodes, the 5th level couldn't be completely filled. The rest was just figuring out how many nodes in the 4th level could be nodes, and how many could be leaves.