recategorized by
783 views
2 votes
2 votes

A full binary tree with $n$ non-leaf nodes contains

  1. $\log_ 2 n$ nodes
  2. $n+1$ nodes
  3. $2n$ nodes
  4. $2n+1$ nodes
recategorized by

2 Answers

1 votes
1 votes

In full tree , the node will either have 2 or no children. 

Thus 1 node has 2 children

2 node has 4 children

3 nodes have 6 children

hence “n” internal nodes have 2n+1 children (1 for including the root)

1 votes
1 votes
The relationship between external(leaf) nodes and internal nodes for binary tree is: $$L = i +1$$

According to ques, $i = n$ so using formula,

$$L = n+1$$

Since tree is made up of internal and leaf nodes

Therefore, Total no. of nodes(N) = $L +i$

So , $$N = n+1+n$$

$$Ans:N = 2n+1$$
Answer:

Related questions

2 votes
2 votes
2 answers
1
admin asked Apr 2, 2020
1,064 views
A hash table with $10$ buckets with one slot per bucket is depicted. The symbols, $S1$ to $S7$ are initially emerged using a hashing function with linear probing. Maximum...
1 votes
1 votes
1 answer
2
admin asked Apr 2, 2020
685 views
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is$\Theta (\lo...