Consider the following algorithm: Algorithm T(r) Input: Root r of a proper binar

Question

Consider the following algorithm: Algorithm T(r) Input: Root r of a proper binary tree. if r is a leaf then return 0 else {p leftarrow T(left child of r) q leftarrow T(right child of r) return p + q + 1} What does the algorithm compute? The number of nodes in the tree. The number of internal nodes in the tree. The number of leaves in the tree. The height of the tree. The number of descendants of r. The smallest AVL-tree of height 1 has 1 key ("smallest" here means the smallest AVL-tree of height 2 has 2 keys, and the smallest AVL tree of height 3 has keys How many keys does the smallest AVL-tree of height 5 have? 10 11 12 13 14

Explanation / Answer

Hi,

1)B

an internal node means a node of tree which has atleast one child node ,i have drawn a basic tree and applied the algorithm on it. all the other options are contradicting it is the answer.

at the child node it will return zero and so if it went till the node that exact node will return 1 i will upload my piece of work i have done on paper

2)the formula for this question is

n(h)=n(h1)+n(h2)+1 where h is the height and n(1)=2 and n(0)=1

if we recrusively reduce the number and substitute the final value the answer will come

so the answer is c 14

please refer the image below to check the process

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---