What is the minimum and maximum number of nodes in a complet

What is the minimum and maximum number of nodes in a complete tree of height 6? b) What is the minimum number of nodes in a balanced AVL tree of height 4? c) What is the maximum number of leaf nodes in a binary tree of height h? d) What is the height of node C in the tree shown below? e) Given a BST, find which value is the median value, and delete that value? f) Insert into a Dictionary implemented with an AVL tree.

Solution

a)
Given h=6
The mininum number of nodes in tree of height h = h+1
nodes = h+1 = 6+1 = 7 nodes

The maximum number of nodes of height h is 2^h+1 - 1
nodes = 2^(6+1) - 1 ===> 2^7 - 1 ==> 128-1 = 127 nodes

---------------------------------------------------------------------------------------------
b) minimum node sin AVL tree of height 4 is :
S(k) = 1 + S(k-1) + S(k-2) where S(0) = 1, S(1) = 2
S(4) = 1 + S(4-1) + S(4-2) = 1 + S(3) + S(2)
==> 1 + 1 + S(3-1) + S(3-2) + S(2) ==> 2 + S(2) + S(1) + S(2)
   ==> 2 + 4 + 2 + 4 ==> 12 nodes
  
---------------------------------------------------------------------------------------------
c)
minimum number of leaf nodes in binary tree of height h is 2^h

-------------------------------------------------------------------------------------------------
d)
Height of given tree is 5

------------------------------------------------------------------------------------------
e)
index=0 //id is a global variable
getMedian(node):
if node == null:
return null
temp = getMedian(node.left)
if temp != null:
return temp
if index == n/2:
return node
index = index + 1
return getMedian(node.right)  

*** return median value we will delete using delete() function
---------------------------------------------------------------------------------------------------
f)
Node *insertNode(Node **node, String val)
{
if (*node == NULL) {
*node = new Node(val);
return *node;
}

if (val < (*node)->val)
return insertNode(&(*node)->left, val);

if (val > (*node)->val)
return insertNode(&(*node)->right, val);

return *node;
}