Tree Flashcards
What is full binary tree
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.
What is complete binary tree
A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.
A complete binary tree is just like a full binary tree, but with two major differences
All the leaf elements must lean towards the left.
The last leaf element might not have a right sibling i.e. a complete binary tree doesn’t have to be a full binary tree.
Which of the following is a true about Binary Trees
A
Every binary tree is either complete or full.
B
Every complete binary tree is also a full binary tree.
C
Every full binary tree is also a complete binary tree.
D
No binary tree is both complete and full.
E
None of the above
E
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
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 multi-stage decision-making, like Chess Game.
6) As a workflow for compositing digital images for visual effects
A
1, 2, 3, 4 and 6
B
1, 2, 3, 4 and 5
C
1, 3, 4, 5 and 6
E
1, 2, 3, 4, 5 and 6
E
The maximum number of binary trees that can be formed with three unlabelled nodes is:
(A) 1
(B) 5
(C) 4
(D) 3
Answer: (B)
Explanation: Following are all possible unlabeled binary trees
O
/ \
O O
(i)
O
/
O
/
O
(ii)
O
/
O
\
O
(iii)
O
\
O
\
O
(iv)
O
\
O
/
O
(v)
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 = (2nCn)/ n+1
= (2*3C3)/ 4+1
= 5.
So, option (B) is correct.
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is: A n/2 B (n-1)/3 C (n-1)/2 D (2n+1)/3
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
A complete n-ary 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 n-ary tree. If L = 41, and I = 10, what is the value of n? (A) 6 (B) 3 (C) 4 (D) 5
Answer: (D)
Explanation: 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
A binary tree T has 20 leaves. The number of nodes in T having two children is (A) 18 (B) 19 (C) 17 (D) Any number between 10 and 20
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 + kI - k + I -1 + k = 2L + 2I - 2
L + KI + I - 1 = 2L + 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.
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 (A) O(log n) (B) O(n) (C) O (n log log n) (D) O(n log n)
Answer: (B)
Explanation: The above statement is actually algorithm for building a Heap of an input array A.
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
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is: (A) 2h – 1 (B) 2h – 1 + 1 (C) 2h – 1 (D) 2h h is in power
Answer: (B)
Explanation:
Let there be n(h) nodes at height h.
In a perfect tree where every node has exactly
two children, except leaves, following recurrence holds.
n(h) = 2*n(h-1) + 1
In given case, the numbers of nodes are two less, therefore
n(h) = 2n(h-1) + 1 - 2
= 2n(h-1) - 1
Now if try all options, only option (b) satisfies above recurrence.
Let us see option (B)
n(h) = 2h - 1 + 1
So if we substitute
n(h-1) = 2h-2 + 1, we should get n(h) = 2h-1 + 1
n(h) = 2n(h-1) - 1
= 2(2h-2 + 1) -1
= 2h-1 + 1.
