Test: Trees - 1 - Computer Science Engineering (CSE) MCQ

A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

A) is incorrect. For example, the following Binary tree is neither complete nor full

     12
   /  
  20
 /
30
B) is incorrect. The following binary tree is complete but not full

     12
   /   \
  20    30
 /
30
C) is incorrect. Following Binary tree is full, but not complete

     12
   /   \
  20    30
       /  \  
      20   40
D) is incorrect. Following Binary tree is both complete and full

      12
    /   \
   20    30
  /  \  
 10   40

For an k-ary tree where each node has k children or no children, following relation holds
L = (k-1)*n + 1

Where L is the number of leaf nodes and n is the number of internal nodes.
since its a complete k tree, so every internal node will have K child
Let us see following for example

k = 3
Number of internal nodes n = 4
Number of leaf nodes = (k-1)*n + 1
= (3-1)*4 + 1
= 9

Following are all possible unlabeled binary trees

Note that nodes are unlabeled. If the nodes are labeled, we get more number of trees.
We can find the number of binary tree by Catalan number number:
Here n = 3
Number of binary tree = (²ⁿC_n)/ n+1
= (2^*3C₃)/ 4+1
= 5.
So, option (B) is correct.

Let L be the number of leaf nodes and I be the number of internal nodes, then following relation holds for above given tree.

  L = (3-1)I + 1 = 2I + 1
Total number of nodes(n) is sum of leaf nodes and internal nodes

  n = L + I
After solving above two, we get L = (2n+1)/3

For an n-ary tree where each node has n children or no children, following relation holds

    L = (n-1)*I + 1
Where L is the number of leaf nodes and I is the number of internal nodes.

Let us find out the value of n for the given data.

  L = 41 , I = 10
  41 = 10*(n-1) + 1
  (n-1) = 4
  n = 5

 For a right skewed binary tree, number of nodes will be 2^{n – 1}. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15.

Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.

(1 (2 3 4)(5 6 7)) represents following binary tree 

A) (1 2 (4 5 6 7)) is not fine as there are 4 elements in one bracket.

B) (1 (2 3 4) 5 6) 7) is not fine as there are 2 opening brackets and 3 closing.

D) (1 (2 3 NULL) (4 5)) is not fine one bracket has only two entries (4 5)

It is mentioned that each node has odd number of descendants including node itself, so all nodes must have even number of descendants 0, 2, 4 so on. Which means each node should have either 0 or 2 children. So there will be no node with 1 child. Hence 0 is answer.

Following are few examples.

       a
    /    \
   b      c

      a
    /   \
   b     c  
  /  \
 d    e
Such a binary tree is full binary tree (a binary tree where every node has 0 or 2 children).

Number of nodes is maximum for a perfect binary tree.
A perfect binary tree of height h has 2h+1 - 1 nodes

Number of nodes is minimum for a skewed binary tree.
A perfect binary tree of height h has h+1 nodes.

Sum of all degrees = 2 * |E|.

Here considering tree as a k-ary tree :

Sum of degrees of leaves + Sum of degrees for Internal Node except root + Root's degree = 2 * (No. of nodes - 1).
Putting values of above terms,
L + (I-1)*(k+1) + k = 2 * (L + I - 1)
L + k*I - k + I -1 + k = 2*L + 2I - 2
L + K*I + I - 1 = 2*L + 2*I - 2
K*I + 1 - I = L
(K-1)*I + 1 = L
Given k = 2, L=20
==> (2-1)*I + 1 = 20
==> I = 19
==> T has 19 internal nodes which are having two children.

The answer to this question is simply max-heapify function. Time complexity of max-heapify is O(Log n) as it recurses at most through height of heap.

// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MaxHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int largest = i;
    if (l < heap_size && harr[l] < harr[i])
        largest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        largest = r;
    if (largest != i)
    {
        swap(&harr[i], &harr[largest]);
        MinHeapify(largest);
    }
}

It would be node number 31 for given distance 4.

For example if we consider at distance 2, below highlighted node G can be the farthest node at position 7.

            A
         /    \
        B       C
       / \     / \
      D   E   F   G
Alternative Solution :
t is the n-th vertex in this BFS traversal at distance four from the root. So height of tree is 4.
Max number of nodes = 2^{h+1} − 1 = 2^{5} − 1 = 31
At distance four, last node is 31. option (C)

The total number of structurally different possible binary trees can be found out using the Catalon number which is (2n)!/ (n! *(n+1)!).
Here n=4, so, answer is 14.

A Binary Tree is full if every node has 0 or 2 children. Following are examples of full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children. A full binary tree with n leaves contains 2 * n – 1 nodes.
So, option (C) is correct.