## Trees

Question 1 |

The number of unused pointers in a complete binary tree of depth 5 is:

4 | |

8 | |

16 | |

32 |

Question 1 Explanation:

It gives ambitious answer. It may give 32 if root start from 0. It start from means 16.

Question 2 |

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

nk | |

(n-1)k+1 | |

n(k-1)+1 | |

n(k-1) |

Question 2 Explanation:

Total nodes = nk+1 (1 for root)

Leaves = total nodes - internal nodes

= nk+1-n

= n(k-1)+1

Leaves = total nodes - internal nodes

= nk+1-n

= n(k-1)+1

Question 3 |

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 |

Question 3 Explanation:

Number of internal nodes= 4+3+3 = 10

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

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

The following figure is a____ tree after zig-zig rotations

Heap | |

Bubble | |

Splay | |

Binary |

Question 4 Explanation:

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.

Question 5 |

A complete n-ary tree is one in which every node has 0 or n children. If there are x internal nodes in a complete n-ary tree, the number of leaves is

(n-1)x+1 | |

(n-1)x-1 | |

nx+1 | |

nx-1 |

Question 5 Explanation:

Consider binary tree with two children.

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

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

Question 6 |

Given a tree with k nodes, the sum of degrees of all nodes is

2 ^{k-1} | |

2*(k-1) | |

2 ^{k+1} | |

2((k+1) |

Question 6 Explanation:

The number of edges in tree with “k” nodes are K-1..

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

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

Question 7 |

Let us assume that you construct ordered tree to represent the compound proposition (~ (p ∧ q)) ↔ (~ p ∨ ~ q) Then, the prefix expression and post-fix expression determined using this ordered tree are given as ____ and _____ respectively.

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

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

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

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

Question 7 Explanation:

Step-1: Given compound proposition is

(~(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~∨↔

(~(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 8 |

In what tree, for every node the height of its left subtree and right subtree differ at least by one :

Binary search tree | |

AVL - tree | |

Threaded binary tree | |

Complete tree |

Question 8 Explanation:

Threaded binary tree: A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers
that would normally be null point to the inorder predecessor of the node.

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

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

Which of the following statement is false ?

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 |

Question 9 Explanation:

A tree never contains cycles. If it contains a cycle, we are calling as graph but not tree.

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

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

Question 10 |

Preorder is also known as :

Depth first order | |

Breadth first order | |

Topological order | |

Linear order |

Question 10 Explanation:

Preorder is also known as topological order. Every preorder can be given a topology, and indeed, every preorder on a set is in one-to-one correspondence with an topology on that set.

Question 11 |

Which of the following statement is false ?

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 |

Question 11 Explanation:

A tree never contains cycles. If it contains a cycle, we are calling as graph but not tree.

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

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

Question 12 |

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 |

Question 12 Explanation:

Number of internal nodes= 4+3+3= 10

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.

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

Consider the following minimax game tree search

What will be the value propagated at the root ?

What will be the value propagated at the root ?

6 | |

3 | |

5 | |

4 |

Question 13 Explanation:

Question 14 |

A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be :

30 | |

33 | |

45 | |

None of the above |

Question 14 Explanation:

L = I(n-1)+ 1

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

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

Which of the following does not define a tree ?

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

Question 15 Explanation:

→ An undirected graph is

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

**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 16 |

Consider a rooted tree in which every node has at least three children. What is the minimum number of nodes at level i (i > 0) of the tree ? Assume that the root is at level 0 :

3 ^{i} | |

3i | |

3 | |

3i + 1 |

Question 16 Explanation:

From the given question,

Given condition is every node has at least three children.

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

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

at level 2, nine nodes will be present (3

and so on the at level "i", 3

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.
There are 16 questions to complete.