M-ary Tree: Given Nodes, find leaves

  • Thread starter Thread starter scorpius1782
  • Start date Start date
  • Tags Tags
    Nodes Tree
Click For Summary

Discussion Overview

The discussion revolves around determining the number of leaves in a 4-ary tree with a total of 173 nodes. Participants explore various methods and reasoning to arrive at a solution, sharing their attempts and challenges in visualizing and calculating the tree structure.

Discussion Character

  • Homework-related
  • Exploratory
  • Mathematical reasoning

Main Points Raised

  • One participant suggests that each non-leaf node in a 4-ary tree has 4 children, leading to a belief that there should be a straightforward method to calculate the number of leaves.
  • Another participant proposes counting nodes at each level, noting that the number of nodes increases exponentially with each level, but expresses uncertainty about how many nodes at the fourth level are leaves.
  • Some participants calculate the total number of nodes up to the fourth level and infer that the remaining nodes must be in the fifth level, leading to the conclusion that some fourth-level nodes must be leaves.
  • There are conflicting calculations regarding the number of leaves and nodes at the fourth level, with participants correcting each other and revising their previous statements.
  • One participant emphasizes the technique of counting nodes at each level and running totals, suggesting that the total number of nodes in the fifth level cannot be fully filled based on the total node count.

Areas of Agreement / Disagreement

Participants express differing views on the exact number of leaves and nodes at various levels, leading to an unresolved discussion with multiple competing interpretations and calculations.

Contextual Notes

Participants rely on assumptions about the distribution of nodes across levels and the definition of leaves, which may not be fully articulated or agreed upon. The calculations involve some uncertainty and corrections as participants refine their reasoning.

scorpius1782
Messages
107
Reaction score
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??
 
Physics news on Phys.org
scorpius1782 said:

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.
 
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.
 
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.
 
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?
 
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:
Mark44 said:
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.
 
I wrote 46, but meant 42. It was pretty late when I wrote that. It is now corrected in my earlier post.
 
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
 
  • #10
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.
 

Similar threads

Algorithm for computing the depths of all the nodes of tree
  • · Replies 1 ·
Replies
1
Views
3K
Proving the Number of Leaves is One More Than Internal Nodes in Binary Trees
  • · Replies 1 ·
Replies
1
Views
2K
Comp Sci Number of trees in a Fibonacci Heap without CASCADING-CUT
  • · Replies 11 ·
Replies
11
Views
2K
Engineering Why is the voltage source high potential into node 1 at -12 V in this op amp problem?
  • · Replies 15 ·
Replies
15
Views
3K
Undergrad How do leaf nodes behave in regression decision trees?
  • · Replies 6 ·
Replies
6
Views
3K
Mathematical Induction in binary trees
  • · Replies 6 ·
Replies
6
Views
2K
How can the countability of binary trees be proven?
  • · Replies 1 ·
Replies
1
Views
2K
Internal Path Length: Solving the Mystery
  • · Replies 13 ·
Replies
13
Views
2K
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Do we have stack involvement in a threaded tree?
  • · Replies 4 ·
Replies
4
Views
2K