- #1
scorpius1782
- 107
- 0
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??