Consider a rooted n node binary tree represented using pointers.

Home » Programming & Data Structure » Programming and data structure miscellaneous » Question

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O (n^a log^bn). Then the value of a + 10b is ______.

1. 0
2. 1
3. 1 to 1
4. None of these

Correct Option: C

1 to 1
Value of a + 10b = 1.
We can find the subtree with 4 nodes in O(n) time, we can use following Algorithm :
(1) Transverse the tree in bottom up manner and find size of subtree rooted with current node.
(2) If size becomes 4, then print the current node. int print 4 subtree (struct Node *root)
{
   if (root = = NULL)
   return 0;
   int l = print 4 subtree (root → left);
   int r = print 4 subtree (root → right);
   if ((l + r + 1) = = 4)
   printf (“%d”, root ® data);
   return (l + r + 1)
}