0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A full binary tree (sometimes referred to as a proper[15] or plane binary tree)[16][17] is a tree in which every node in the tree has either 0 or 2 children. en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees don't you think it is 85 instead of 58 ? $\endgroup$ – reuns Jan 11 '16 at 9:13
  • $\begingroup$ Ah ok, so but how many leaves are there now? no it is 58. $\endgroup$ – vicR Jan 11 '16 at 9:23
  • $\begingroup$ A full $4$-ary tree means every node has up to $4$ children. $\endgroup$ – Eli Rose Jan 11 '16 at 9:31
1
$\begingroup$

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?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.