Which of the following is a true about Binary Trees?
A full binary tree (sometimes proper binary tree or 2tree 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
If arity of operators is fixed, then which of the following notations can be used to parse expressions without parentheses?
(a) Infix Notation (Inorder traversal of a expression tree)
(b) Postfix Notation (Postorder traversal of a expression tree)
(c) Prefix Notation (Preorder traversal of a expression tree)
Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is ____.
In the following answers, the operator '^' indicates power.
2^(i1) where i ≧1. Proof: by Induction,
• Introduction base: i=1 (root) The number of node is: 2^(i1) = 2^0 = 1.
• Induction hypothesis Assume that for i ≧1, the maximum number of nodes on level i1 is 2^(i2).
• 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^(i2) which is 2^(i1)
In a complete kary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is:
For an kary tree where each node has k children or no children, following relation holds L = (k1)*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 = (k1)*n + 1
= (31)*4 + 1
= 9
The maximum number of binary trees that can be formed with three unlabeled nodes is:
Note that nodes are unlabeled. If the nodes are labeled, we get more number of trees.
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
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 = (31)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
A weightbalanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?
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.
A complete nary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete nary tree. If L = 41, and I = 10, what is the value of n?
For an nary tree where each node has n children or no children, following relation holds
L = (n1)*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*(n1) + 1
(n1) = 4
n = 5
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
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} + 2*3 + …. 2^{h} = 2^{(h+1)} – 1
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.
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.
Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?
Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.
Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
(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)
Consider a node X in a Binary Tree. Given that X has two children, let Y be Inorder successor of X. Which of the following is true about Y?
Since X has both children, Y must be leftmost node in right child of X.
In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
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).
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
Below is the given tree.
The height of a tree is the length of the longest roottoleaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are:
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.
A binary tree T has 20 leaves. The number of nodes in T having two children is
Sum of all degrees = 2 * E. Here considering tree as a kary 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 + (I1)*(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
(K1)*I + 1 = L
Given k = 2, L=20
⇒ (21)*I + 1 = 20
⇒ I = 19
⇒ T has 19 internal nodes which are having two children.
Consider a complete binary tree where the left and the right subtrees of the root are maxheaps. The lower bound for the number of operations to convert the tree to a heap is
The answer to this question is simply maxheapify function. Time complexity of maxheapify 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);
}
}
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n – 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n – 1)/2⌋, ⌊(n – 3)/ 2⌋, ….., 0. The time required to construct a heap in this manner is:
BUILDHEAP(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
What are the main applications of tree data structure?
1) Manipulate hierarchical data.
2) Make information easy to search (see tree traversal).
3) Manipulate sorted lists of data.
4) Router algorithms.
5) Form of a multistage decisionmaking, like Chess Game.
6) As a workflow for compositing digital images for visual effects
Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 








