## Trees

Question 1 |

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.

1 | |

2 | |

3 | |

4 |

In – 8 6 9 4 7 2 5 1 3

Post: 8 9 6 7 4 5 2 3

__1__→(root)

In: 8 6 9 4 7 2

__5__→(left subtree)

__13__→(right subtree)

Question 2 |

Let *T *be a tree with 10 vertices. The sum of the degrees of all the vertices in *T* is _________.

18 | |

19 | |

20 | |

21 |

A tree, with 10 vertices, consists n - 1, i.e. 10 - 1 = 9 edges.

Sum of degrees of all vertices = 2(#edges)

= 2(9)

= 18

Question 3 |

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _________.

*Note: The height of a tree with a single node is 0.*

64 | |

65 | |

66 | |

67 |

So to get such tree at each level we should have either maximum or minimum element from remaining numbers till that level. So no. of binary search tree possible is,

1

^{st}level - 2 (maximum or minimum)

⇓

2

^{nd}level - 2

⇓

3

^{rd}level - 2

⇓

4

^{th}level - 2

⇓

5

^{th}level - 2

⇓

6

^{th}level - 2

⇓

7

^{th}level - 2

= 2 × 2 × 2 × 2 × 2 × 2 × 1

= 2

^{6}

= 64

Question 4 |

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

63 and 6, respectively | |

64 and 5, respectively | |

32 and 6, respectively | |

31 and 5, respectively |

2

^{h+1}- 1 = 2

^{5+1}- 1 = 63

Minimum number of nodes in a binary tree of height h is

h + 1 = 5 + 1 = 6

Question 5 |

Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting G in the above tree?

None of the above |

Insert G at root level:

Question 6 |

A 2-3 tree is tree such that

- (a) all internal nodes have either 2 or 3 children

(b) all paths from root to the leaves have the same length

The number of internal nodes of a 2-3 tree having 9 leaves could be

4 | |

5 | |

6 | |

7 | |

Both A and D |

Where L is leaf node.

So, no. of internal node is 4.

Case 2:

Where L is leaf node.

So, no. of internal node is 7.

Question 7 |

4 | |

8 | |

16 | |

32 |

Question 8 |

**In a complete k-array, every internal node has exactly k children. The number of leafs in such a tree with n internal nodes is**

nk | |

(n-1)k+1 | |

n(k-1)+1 | |

n(k-1) |

Leaves = total nodes - internal nodes

= nk+1-n

= n(k-1)+1

Question 9 |

In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is

11 | |

12 | |

10 | |

9 |

Number of leaf nodes = Sum of degrees of all internal nodes - number of internal nodes +1

= (4*1 + 3*2 + 3*3 ) - 10 + 1

= 19 - 10 + 1

= 10

**Formula**: nd - n + 1 where n is number of nodes and d is degree of the tree.

Question 10 |

Heap | |

Bubble | |

Splay | |

Binary |

Question 11 |

(n-1)x+1 | |

(n-1)x-1 | |

nx+1 | |

nx-1 |

Then n value is 2 and internal node is 1 then the number of leaves are (2-1)1+1=2 leaves.

Question 12 |

2 ^{k-1} | |

2*(k-1) | |

2 ^{k+1} | |

2((k+1) |

According to the handshaking lemma , the sum of the degree is 2* number of edges So the option B is suitable one.

Question 13 |

↔~∧pq∨ ~ ~ pq, pq∧~p~q~∨↔ | |

↔~∧pq∨ ~ p~q, pq∧~p~q~∨↔ | |

↔~∧pq∨ ~ ~ pq, pq∧~p~~q∨↔ | |

↔~∧pq∨ ~ p~ q, pq∧~p~ ~q∨↔ |

(~(p ∧ q))↔(~ p ∨ ~ q)

It is clearly specifying that

↔ is a root

(~(p ∧ q)) is left subtree

(~p ∨ ~q) is right subtree.

Step-2: Finally the tree is looks like

Step-3: Prefix operation traverse through Root,left and Right ↔~∧pq∨ ~ p~q Step-4: Postfix operation traverse through Left,Right and Root.

pq∧~p~q~∨↔

Question 14 |

Binary search tree | |

AVL - tree | |

Threaded binary tree | |

Complete tree |

1. Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right).

2. Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right).

Question 15 |

Every tree is a bipartite graph | |

A tree contains a cycle | |

A tree with n nodes contains n-1 edges | |

A tree is a connected graph |

Note: Minimum 1 edge and maximum n-1 edges.

Question 16 |

Depth first order | |

Breadth first order | |

Topological order | |

Linear order |

→ A depth-first order is defined to be the reverse of the order in which we last visit the nodes of the control graph when we create the Depth first spanning tree(DFST).

Question 17 |

Every tree is a bipartite graph | |

A tree contains a cycle | |

A tree with n nodes contains (n-1) edges | |

A tree is connected graph |

Note: Minimum 1 edge and maximum n-1 edges.

Question 18 |

11 | |

12 | |

10 | |

9 |

Number of leaf nodes = Sum of degrees of all internal nodes - number of internal nodes +1

= (4*1 + 3*2 + 3*3 )-10 +1

= 19- 10 +1=10

Formula : nd-n +1 where n is number of nodes and d is degree of the tree.

Question 19 |

What will be the value propagated at the root ?

6 | |

3 | |

5 | |

4 |

Question 20 |

30 | |

33 | |

45 | |

None of the above |

Where, L= Number of leaf nodes

n= N-ary tree

I = Number of intermediate nodes

Now, L =8(5-1)+1

L =8(4)+1

L =33

Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes

Total Number of nodes in a tree = 8+33

Total Number of nodes in a tree = 41

Question 21 |

A tree is a connected acyclic graph. | |

A tree is a connected graph with n-1 edges where ‘n’ is the number of vertices in the graph. | |

A tree is an acyclic graph with n-1 edges where ‘n’ is the number of vertices in the graph. | |

A tree is a graph with no cycles. |

**connected**when there is a path between every pair of vertices. In a connected graph, there are no

**unreachable**vertices. A graph that is not connected is

**disconnected**. An undirected graph G is said to be

**disconnected**if there exist two nodes in G such that no path in G has those nodes as endpoints.

→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.

→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).

→ All first 3 options are correctly defining tree without any loss of information, whereas "A tree is a graph with no cycles." is not always correct as it can be bipartite.

Hence D does not define a tree.

Question 22 |

3 ^{i} | |

3i | |

3 | |

3i + 1 |

Given condition is every node has at least three children.

the root node is present at level 0, here only one is present(3

^{0})

at level 1, three nodes are present based upon the condition( 3

^{1}nodes)

at level 2, nine nodes will be present (3

^{2}nodes ) [Each node has at least three children]

and so on the at level "i", 3

^{i}nodes will be present.

Question 23 |

Which of the following is the Postorder traversal of the binary tree whose tree Inorder and Preorder traversals are as follows?

In-order : OLCHJBEKNGMADFI

Preorder: KHLOCBJEAGNMFDI

ADFLIBNCJEMGHOK | |

OCLJEBGDIAFNMHK | |

ADFLIBNMGJCEHOK | |

OCLJEBHNMGDIFAK |

Inorder: OLCHJBEKNGMADFI

Preorder: KHLOCBJEAGNMFDI

→ Inorder = Left_child, Root, Right_child

Preorder = Root, Left_child, Right_child

Postorder = Left_child, Right_child, Root

→ Since in Pre-order ‘K’ is at 1st position so ‘K’ is the root of the Binary tree.

→ And in In-order if you will see then OLCHJBE are in its LHS and NGMADFI are in its RHS.

Question 24 |

Match the following.

I-S, II-R, III-P, IV-Q | |

I-S, II-Q, III-P, IV-R | |

I-S, II-P, III-Q, IV-R | |

I-P, II-Q, III-R, IV-S |

→Tree and Graph are examples of non-linear data structure.

→A binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

Question 25 |

1/N | |

N-1/N | |

1/K | |

K-1/K |

Ratio of internal nodes to the total nodes = n/(nk + 1)

= 1/k

Question 26 |

The Leaves of a tree

Are those nodes with single child.
| |

Is the maximum length of a branch from the root to leaf.
| |

Are those nodes with no children.
| |

Are those nodes have same parent. |

Question 27 |

Stack | |

Queue | |

Tree | |

All the above |

Question 28 |

N/2 | |

N | |

Log N | |

1 |