1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

M-ary Tree: Given Nodes, find leaves

  1. Mar 30, 2014 #1
    1. The problem statement, all variables and given/known data
    (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?


    2. Relevant equations



    3. 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??
     
  2. jcsd
  3. Mar 31, 2014 #2

    Mark44

    Staff: Mentor

    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.
     
  4. Mar 31, 2014 #3
    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.
     
  5. Mar 31, 2014 #4

    Mark44

    Staff: Mentor

    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.
     
  6. Apr 1, 2014 #5
    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?
     
  7. Apr 1, 2014 #6

    Mark44

    Staff: Mentor

    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.
     
    Last edited: Apr 1, 2014
  8. Apr 1, 2014 #7
    But, that would make 68 nodes in level 4.
     
  9. Apr 1, 2014 #8

    Mark44

    Staff: Mentor

    I wrote 46, but meant 42. It was pretty late when I wrote that. It is now corrected in my earlier post.
     
  10. Apr 1, 2014 #9
    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
     
  11. Apr 1, 2014 #10

    Mark44

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: M-ary Tree: Given Nodes, find leaves
Loading...