[Math] Full 4-ary tree with 58 internal nodes

discrete mathematicstrees

I'm not sure how to answer this question

In a full 4-ary tree, there are 58 internal nodes. What is the number
of leaf nodes in this tree?

So a full 4-ary tree means every node has 0 or 4 childs; there are 58 internal nodes; leaf nodes are nodes without children; does it mean there are 58 internal nodes and every longest path node (not to the leaf to the internal node) has 4 childs so 4 leaf nodes because the tree is full ? Or empty.

thx for any help.

Best Answer

HINT: No, each node of a full $4$-ary tree has $0$ or $4$ nodes. An internal node cannot have $0$ children, so it must have $4$ children. That means that there are $4$ edges from it to its children. Every edge of the tree runs from an internal node to one of its children, so the tree must have $4\cdot 58=232$ edges.

  • How many nodes does a tree with $232$ edges have?
  • If $58$ of those nodes are internal, how many are leaves?
Related Question