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

 A 1 B 2 C 3 D 4
Data-Structures       Trees       GATE 2018
Question 1 Explanation:
Post – 8 9 6 7 4 5 2 3 1
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 _________.

 A 18 B 19 C 20 D 21
Data-Structures       Trees       GATE 2017 [Set-1]
Question 2 Explanation:
Sum of degrees of all vertices is double the number of edges.
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.
 A 64 B 65 C 66 D 67
Data-Structures       Trees       GATE 2016 [Set-2]
Question 3 Explanation:
To get the tree of height 6, every level should contain only 1 node.
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,
1st level - 2 (maximum or minimum)

2nd level - 2

3rd level - 2

4th level - 2

5th level - 2

6th level - 2

7th level - 2
= 2 × 2 × 2 × 2 × 2 × 2 × 1
= 26
= 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

 A 63 and 6, respectively B 64 and 5, respectively C 32 and 6, respectively D 31 and 5, respectively
Data-Structures       Trees       GATE 2015 [Set-1]
Question 4 Explanation:
Maximum number of nodes in a binary tree of height h is,
2h+1 - 1 = 25+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?

 A B C D None of the above
Data-Structures       Trees       GATE 2003
Question 5 Explanation:
Given Tree is 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

 A 4 B 5 C 6 D 7 E Both A and D
Data-Structures       Trees       GATE 1992
Question 6 Explanation:
Case 1: 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
The number of unused pointers in a complete binary tree of depth 5 is:
 A 4 B 8 C 16 D 32
Data-Structures       Trees       Nielit Scientist-B IT 4-12-2016
Question 7 Explanation:
It gives ambitious answer. It may give 32 if root start from 0. It start from means 16.
 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
 A nk B (n-1)k+1 C n(k-1)+1 D n(k-1)
Data-Structures       Trees       Nielit Scientist-B CS 22-07-2017
Question 8 Explanation:
Total nodes = nk+1 (1 for root)
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

 A 11 B 12 C 10 D 9
Data-Structures       Trees       UGC-NET DEC Paper-2
Question 9 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.
 Question 10
The following figure is a____ tree after zig-zig rotations A Heap B Bubble C Splay D Binary
Data-Structures       Trees       KVS DEC-2013
Question 10 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 11
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
 A (n-1)x+1 B (n-1)x-1 C nx+1 D nx-1
Data-Structures       Trees       KVS 30-12-2018 Part B
Question 11 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.
 Question 12
Given a tree with k nodes, the sum of degrees of all nodes is
 A 2k-1 B 2*(k-1) C 2k+1 D 2((k+1)
Data-Structures       Trees       KVS 30-12-2018 Part B
Question 12 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.
 Question 13
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.
 A ↔~∧pq∨ ~ ~ pq, pq∧~p~q~∨↔ B ↔~∧pq∨ ~ p~q, pq∧~p~q~∨↔ C ↔~∧pq∨ ~ ~ pq, pq∧~p~~q∨↔ D ↔~∧pq∨ ~ p~ q, pq∧~p~ ~q∨↔
Algorithms       Trees       UGC NET CS 2016 Aug- paper-2
Question 13 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~∨↔
 Question 14
In what tree, for every node the height of its left subtree and right subtree differ at least by one :
 A Binary search tree B AVL - tree C Threaded binary tree D Complete tree
Data-Structures       Trees       UGC NET CS 2005 Dec-Paper-2
Question 14 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).
 Question 15
Which of the following statement is false ?
 A Every tree is a bipartite graph B A tree contains a cycle C A tree with n nodes contains n-1 edges D A tree is a connected graph
Data-Structures       Trees       UGC NET CS 2005 june-paper-2
Question 15 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.
 Question 16
Preorder is also known as :
 A Depth first order B Breadth first order C Topological order D Linear order
Data-Structures       Trees       UGC NET CS 2006 June-Paper-2
Question 16 Explanation:
→ Pre order is also known as depth first 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
Which of the following statement is false ?
 A Every tree is a bipartite graph B A tree contains a cycle C A tree with n nodes contains (n-1) edges D A tree is connected graph
Data-Structures       Trees       UGC NET CS 2006 June-Paper-2
Question 17 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.
 Question 18
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
 A 11 B 12 C 10 D 9
Algorithms       Trees       UGC NET CS 2018-DEC Paper-2
Question 18 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.
 Question 19
​ Consider the following minimax game tree search What will be the value propagated at the root ?
 A 6 B 3 C 5 D 4
Data-Structures       Trees       UGC NET CS 2018-DEC Paper-2
Question 19 Explanation: Question 20
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 :
 A 30 B 33 C 45 D None of the above
Data-Structures       Trees       UGC NET CS 2018 JUNE Paper-2
Question 20 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
 Question 21
Which of the following does not define a tree ?
 A A tree is a connected acyclic graph. B A tree is a connected graph with n-1 edges where ‘n’ is the number of vertices in the graph. C A tree is an acyclic graph with n-1 edges where ‘n’ is the number of vertices in the graph. D A tree is a graph with no cycles.
Data-Structures       Trees       UGC NET CS 2008-june-Paper-2
Question 21 Explanation:
→ An undirected graph is 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
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 :
 A 3i B 3i C 3 D 3i + 1
Data-Structures       Trees       UGC NET CS 2007-Dec-Paper-2
Question 22 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(30)
at level 1, three nodes are present based upon the condition( 31 nodes)
at level 2, nine nodes will be present (32 nodes ) [Each node has at least three children]
and so on the at level "i", 3i 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?

Preorder: KHLOCBJEAGNMFDI
Data-Structures       Trees       CIL Part - B
Question 23 Explanation:

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. A I-S, II-R, III-P, IV-Q B I-S, II-Q, III-P, IV-R C I-S, II-P, III-Q, IV-R D I-P, II-Q, III-R, IV-S
Data-Structures       Trees       CIL Part - B
Question 24 Explanation:
→Array,Stack and Queue are examples of linear data structure .
→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
Of the following, which best approximately the ratio of the number of nonterminal nodes in the total number of nodes in a complete K-ary tree of depth N?
 A 1/N B N-1/N C 1/K D K-1/K
Data-Structures       Trees       ISRO CS 2020
Question 25 Explanation: Ratio of internal nodes to the total nodes = n/(nk + 1)
= 1/k
 Question 26

The Leaves of a tree

 A Are those nodes with single child. B Is the maximum length of a branch from the root to leaf. C Are those nodes with no children. D Are those nodes have same parent.
Data-Structures       Trees       APPSC-2012-DL CA
Question 26 Explanation:
The leaves of a tree are those nodes with no children.
 Question 27
Which of the following is a nonlinear data structure?
 A Stack B Queue C Tree D All the above
Data-Structures       Trees       APPSC-2012-DL-CS
Question 27 Explanation:
Stack and queue are linear data structure, but tree is a non linear data structure.
 Question 28
The maximum depth that a tree of N nodes can have is
 A N/2 B N C Log N D 1
Data-Structures       Trees       APPSC-2012-DL-CS
Question 28 Explanation:
The maximum depth that a tree of N nodes can have is N,when the tree is skewed.
There are 28 questions to complete.