Binary Tree

Question 1
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.

The value of |A-B| is _____________
A
3
B
4
C
1
D
2
GATE CSE 2021 SET-2   Data Structure
Question 2
The post-order traversal of binary tree is ACEDBHIGF. The pre-order traversal is
A
A B C D E F G H I
B
F B A D C E G I H
C
F A B C D E G H I
D
A B D C E F G I H
ISRO CSE 2020   Data Structure
Question 3
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________ .
A
2.5
B
4.25
C
6.5
D
3.75
GATE CSE 2019   Data Structure
Question 4


Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?
A
Preorder, postorder
B
Postorder, inorder
C
Postorder, preorder
D
None of these
ISRO CSE 2018   Data Structure
Question 5
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
4
B
5
C
3
D
6
GATE CSE 2018   Data Structure
Question 6


If the post order traversal gives ab -cd * + then the label of the nodes 1,2,3.. will be
A
+ , -, *, a,b,c,d
B
a, -,b,+,c,*,d
C
a,b,c,d,-,*,+
D
-,a,b,+,*,c,d
ISRO CSE 2017   Data Structure
Question 7
A complete binary tree with n non-leaf nodes contains
A
\log_{2}n nodes
B
n+1 nodes
C
2n nodes
D
2n+1 nodes
ISRO CSE 2016   Data Structure
Question 8
Consider the following New-order strategy for traversing a binary tree:
Visit the root;
Visit the right sub tree using New-order;
Visit the left sub tree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish expression
3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:
A
+ -167*2^5-34*
B
- +1*67^2-5*34
C
- +1*76^2-5*43
D
1 76*+2543*-^-
GATE CSE 2016 SET-2   Data Structure
Question 9
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.
A
99
B
100
C
199
D
149
GATE CSE 2015 SET-3   Data Structure
Question 10
A binary tree T has 20 leaves. The number of nodes in T having two children is _______.
A
20
B
19
C
39
D
9
GATE CSE 2015 SET-2   Data Structure
There are 10 questions to complete.

5 thoughts on “Binary Tree”

Leave a Comment