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$
3
  • $\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, 2016 at 9:13
  • $\begingroup$ Ah ok, so but how many leaves are there now? no it is 58. $\endgroup$
    – vicR
    Jan 11, 2016 at 9:23
  • $\begingroup$ A full $4$-ary tree means every node has up to $4$ children. $\endgroup$
    – Eli Rose
    Jan 11, 2016 at 9:31

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .