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

(B) is incorrect. The following binary tree is complete but not full

(C) is incorrect. Following Binary tree is full, but not complete

(D) is incorrect. Following Binary tree is both complete and full

• Polish notation (PN), also known as normal Polish notation (NPN), Lukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators precede their operands, in contrast to reverse Polish notation (RPN) in which operators follow their operands. It does not need any parentheses as long as each operator has a fixed number of operands. The description "Polish" refers to the nationality of logician Jan Lukasiewicz, who invented Polish notation in 1924.
• The term Polish notation is sometimes taken (as the opposite of infix notation) to also include reverse Polish notation.
• When Polish notation is used as a syntax for mathematical expressions by programming language interpreters, it is readily parsed into abstract syntax trees and can, in fact, define a one-to-one representation for the same. Because of this, Lisp (see below) and related programming languages define their entire syntax in terms of prefix notation (and others use postfix notation).

2^(i-1) where i ≧1. Proof: by Induction,
• Introduction base: i=1 (root) The number of node is: 2^(i-1) = 2^0 = 1.
• Induction hypothesis Assume that for i ≧1, the maximum number of nodes on level i-1 is 2^(i-2).
• Induction step Since each node in a binary tree has a maximum degree of 2. Therefore, the maximum number of nodes on level i is 2*2^(i-2) which is 2^(i-1)

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. 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

Note that nodes are unlabeled. If the nodes are labeled, we get more number of trees.

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

Let the maximum possible height of a tree with n nodes is represented by H(n). The maximum possible value of H(n) can be approximately written using following recursion

H(n) = H(2n/3) + 1

The solution of above recurrence is . We can simply get it by drawing a recursion tree. 

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

Maximum number of nodes will be there for a complete tree.
Number of nodes in a complete tree of height h = 1 + 2 + 2² + 2*3 + …. 2^h = 2^(h+1) – 1

For a right skewed binary tree, number of nodes will be 2ⁿ - 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)

Since X has both children, Y must be leftmost node in right child of X.

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.

Such a binary tree is full binary tree (a binary tree where every node has 0 or 2 children).

Below is the given tree.
 

Number of nodes is maximum for a perfect binary tree. A perfect binary tree of height h has 2^h+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);
 }
}

BUILD-HEAP(A) 

    heapsize := size(A); 

    for i := floor(heapsize/2) downto 1 

        do HEAPIFY(A, i); 

    end for 

END

Upper bound of time complexity is O(n) for above algo