topic – RBR

Binary-Trees

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder traversal of the tree?

A	20, 19, 18, 16, 15, 12, 11, 10
B	11, 12, 10, 16, 19, 18, 20, 15
C	10, 11, 12, 15, 16, 18, 19, 20
D	19, 16, 18, 20, 11, 12, 10, 15

Data-Structures Binary-Trees GATE 2020

Question 1 Explanation:

Question 2

What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?

A
B
C
D

Data-Structures Binary-Trees GATE 2020

Question 2 Explanation:

AVL Tree all operations(insert, delete and search) will take O(logn) time.
In question they asked about n² elements.
So, In worst case it will take o(n² logn) time.

Question 3

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.

A
B
C
D

Data-Structures Binary-Trees GATE 2020

Question 3 Explanation:

The idea is to traverse the given binary search tree starting from root. For every node being visited, check if this node lies in range, if yes, then add 1 to result and recur for both of its children. If the current node is smaller than the low value of range, then recur for right child, else recur for left child.
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is logn, hence O(logn+k)

Question 4

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:

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

A	4 and 15 respectively
B	3 and 14 respectively
C	4 and 14 respectively
D	3 and 15 respectively

Engineering-Mathematics Binary-Trees Gate 2017 set-01

Question 4 Explanation:

T be a Binary Search Tree with 15 nodes.
The height of a tree with single node is 0.
Minimum possible height is when it is a complete binary tree.

Maximum possible height is when it is a skewed tree left/right.

So the minimum and maximum possible heights of T are: 3 and 14 respectively.

Question 5

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

A	2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
B	2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
C	7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
D	7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

Data-Structures Binary-Trees GATE 2017(set-02)

Question 5 Explanation:

From these 2 orders, we can say 12 is the root & 8 is the root of left subtree & 16 is the root of right subtree.

From 2, 6, 7 we can identify 6 is the root from preorder traversal and from 9, 10 → 9 is root.
From <17, 19, 20>, 19 as root.

Hence, 2,7,6,10,9,8 |,15,17,20,19,16 |12 is the post-order traversal.

Question 6

Consider the following New-order strategy for traversing a binary tree:

Visit the root;
Visit the right subtree using New-order;
Visit the left subtree 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	+ - 1 6 7 * 2 ˆ 5 - 3 4 *
B	- + 1 * 6 7 ˆ 2 - 5 * 3 4
C	- + 1 * 7 6 ˆ 2 - 5 * 4 3
D	1 7 6 * + 2 5 4 3 * - ˆ -

Data-Structures Binary-Trees GATE 2016 set-2

Question 6 Explanation:

New Order strategy: Root, Right, Left.
Given Reverse Polish Notation as:
3 4 * 5 - 2 ^ 6 7 * 1 + -
We know Reverse Polish Notation takes Left, Right, Root.

So the expression tree looks like

From the tree, we can write the New Order traversal as: Root, Right, Left.
- + 1 * 7 6 ^ 2 - 5 * 4 3

Question 7

A binary tree T has 20 leaves. The number of nodes in T having two children is _________.

A	19
B	20
C	21
D	22

Data-Structures Binary-Trees GATE 2015 -(Set-2)

Question 7 Explanation:

Let the number of vertices of a binary tree with „p‟ leaves be n then the tree has
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e.., root of T) of degree 2
(iii) 'n- p-1' (i.e., interval) vertices of degree 3
(iv) n- 1 edges
∴ By Handshaking theorem,
p×1+1×2+(n-p-1)×3=2(n-1)
⇒n=2p-1
=39 as p=20
∴ n-p=19 vertices have exactly two children

Question 8

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____ .

A	199
B	198
C	197
D	196

Data-Structures Binary-Trees GATE 2015(Set-03)

Question 8 Explanation:

A binary tree T with n leaf nodes have exactly (n - 1) nodes that have exactly two children.

Question 9

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are

A	B1: (1+height(n→right)) B2: (1+max(h1,h2))
B	B1: (height(n→right)) B2: (1+max(h1,h2))
C	B1: height(n→right) B2: max(h1,h2)
D	B1: (1+ height(n→right)) B2: max(h1,h2)

Data-Structures Binary-Trees Gate 2012

Question 9 Explanation:

Now, we analyze the code,
The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.
In such case, height of n will be the height of the right subtree +1.
The box B2 gets executed when both left & right subtrees of n are not NULL.
In such case, height of n will be max of heights of left & right subtrees of n+1.

Question 10

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

A	0
B	1
C	n!
D

Data-Structures Binary-Trees Gate 2011

Question 10 Explanation:

Corresponding to each set only 1 binary search tree can be formed because in-order is fixed. only 1 tree possible. If Binary trees would be asked n! possible corresponding to each distinct tree set. Here tree structure is fixed and have only 1 possibility for BST as elements are distinct.

Question 11

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

A	0
B	1
C	(n-1)/2
D	n-1

Data-Structures Binary-Trees 2010

Question 11 Explanation:

Given a Binary Tree with n nodes.
Every node has an odd number of descendants.
Also given every node is considered to be its own descendant.

― This is even number of descendants (2), because A is also considered as a descendant.

― This is odd number of descendants (3), A, B, C are descendants here.
Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.

Question 12

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. MBCAFHPYK KAMCBYPFH MABCKYFPH Pick the true statement from the following.

A	I and II are preorder and inorder sequences, respectively
B	I and III are preorder and postorder sequences, respectively
C	II is the inorder sequence, but nothing more can be said about the other two sequences
D	II and III are the preorder and inorder sequences, respectively

Data-Structures Binary-Trees Gate 2008-IT

Question 12 Explanation:

In preorder, root comes at the beginning of the traversal sequence and in post order, root comes at last of the traversal sequence.
So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.

Question 13

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I.  81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

A	II and III only
B	I and III only
C	III and IV only
D	III only

Data-Structures Binary-Trees Gate 2008-IT

Question 13 Explanation:

Question 14

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV. 550, 149, 507, 395, 463, 402, 270 Which of the following statements is TRUE?

A	I, II and IV are inorder sequences of three different BSTs
B	I is a preorder sequence of some BST with 439 as the root
C	II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
D	IV is a postorder sequence of some BST with 149 as the root

Data-Structures Binary-Trees Gate 2008-IT

Question 14 Explanation:

A) Incorrect because I & IV are not in ascending order. (Inorder sequence of BST is in increasing order).
B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.

Question 15

A	4
B	5
C	6
D	9

Data-Structures Binary-Trees Gate 2008-IT

Question 15 Explanation:

Formula:

Question 16

A binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n₃ can be expressed as

A
B
C
D

Data-Structures Binary-Trees Gate 2008-IT

Question 16 Explanation:

n₁ = 3
n₂ = 1
n₃ = 1
So, option (B) satisfies.

Question 17

A binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

A	2 * n₁ – 3
B	n₂ + 2 * n₁ – 2
C	n₃ – n₂
D	n₂ + n₁ – 2

Data-Structures Binary-Trees Gate 2008-IT

Question 17 Explanation:

n₁ = 3
n₃ = 1
So, option (A) satisfies.

Question 18

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

A	2^h−1
B	2^h−1 – 1
C	2^h+1– 1
D	2^h+1

Data-Structures Binary-Trees Gate-2007

Question 18 Explanation:

img src = "https://pyq.ravindrababuravula.com/wp-content/uploads/2018/09/5-1.png">
1,3,7,15,31,...=2^h+1 - 1

Question 19

The maximum number of binary trees that can be formed with three unlabeled nodes is:

A	1
B	5
C	4
D	3

Data-Structures Binary-Trees Gate-2007

Question 19 Explanation:

Total number of binary trees possible for n nodes is C(n)=(2n)!/(n+1)!n! C(n)=(2(3))!/(3+1)!3!=6×5×4×3×2×1/4×3×2×1×3×2=5
Total no. of possible trees is 5.

Total = 5

Question 20

The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

A	d e b f g c a
B	e d b g f c a
C	e d b f g c a
D	d e f g b c a

Data-Structures Binary-Trees Gate-2007

Question 20 Explanation:

Inorder: Left root Right
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g

Pre order: a b d e c f g
Post order: d e b f g c a

Question 21

Consider the following C program segment where CellNode represents a node in a binary tree:

struct CellNode 
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};
int GetValue(struct CellNode *ptr) 
{
  int value = 0;
  if (ptr != NULL) 
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value + GetValue(ptr->leftChild)
                   + GetValue(ptr->rightChild);
  }
  return(value);
}



The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

A	the number of nodes in the tree
B	the number of internal nodes in the tree
C	the number of leaf nodes in the tree
D	the height of the tree

Data-Structures Binary-Trees Gate-2007

Question 21 Explanation:

Let take example,

So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.

Question 22

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

A	35
B	64
C	128
D	5040

Data-Structures Binary-Trees Gate 2007-IT

Question 22 Explanation:

To find 60 in BST then there are two possible set i.e., greater than 60 and smaller than 60.
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35

Question 23

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.

A	log₂n
B	n
C	2n+1
D	2ⁿ-1

Data-Structures Binary-Trees Gate-2006

Question 23 Explanation:

The binary right skewed tree follows 2ⁿ -1 because level 2 value is 7 and level 3 value 15.
Note: Assume level numbers are start with 0.

Question 24

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

A	10
B	11
C	12
D	15

Data-Structures Binary-Trees Gate 2006-IT

Question 24 Explanation:

A node in a binary tree has degree 0, 1, 2.
No. of 1 degree nodes = 5
No. of 2 degree nodes = 10
Total no. of edges = (1*5) + (2*10) = 5 + 20 = 25
So, Total no. of edges = 25 + 1 = 26 (No. of nodes in a tree is 1 more than no. of edges)
Total no. of leaf nodes (node with 0 degree) = 26 - 5 - 10 = 11

Question 25

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

A	{10, 75, 64, 43, 60, 57, 55}
B	{90, 12, 68, 34, 62, 45, 55}
C	{9, 85, 47, 68, 43, 57, 55}
D	{79, 14, 72, 56, 16, 53, 55}

Data-Structures Binary-Trees Gate 2006-IT

Question 25 Explanation:

In the binary search tree on right side of parent number, the number should be greater than it. But in option C, after 47, 43 appears. So, this is False.

Question 26

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element X[i],i≠0 is?

A	⌊i/2⌋
B	⌈(i-1)/2⌉
C	⌈i/2⌉
D	⌈i/2⌉ - 1

Data-Structures Binary-Trees Gate 2006-IT

Question 26 Explanation:

If index of array start with 1 then directly divide the i^th value by 2 and take floor. If index start with '0' then ⌈i/2⌉ - 1.

Question 27

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

A	O(n)
B	O(log n)
C	O(n log n)
D	O(n log log n)

Data-Structures Binary-Trees Gate 2006-IT

Question 27 Explanation:

It takes O(log n) to heapify an element of heap.

Question 28

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i ≠ 0, is

A	⌊log₂ i⌋
B	⌈log₂ (i + 1)⌉
C	⌊log₂ (i + 1)⌋
D	⌈log₂ i⌉

Data-Structures Binary-Trees Gate 2006-IT

Question 28 Explanation:

If the root node is at level 0 then the level of element X[i] is ⌊log₂ (i + 1)⌋.

Question 29

A	(i) only
B	(ii), (iii)
C	(iii) only
D	(iv) only

Data-Structures Binary-Trees Gate-2004

Question 29 Explanation:

→We have some combinations such that which can be able to identity a tree
(i) Inorder and Preorder
(ii) Inorder and Postorder
(iii) Inorder and Levelorder
→And following are do not
(i) Post order and Preorder
(ii) Pre order and Level order
(iii) Post order and Level order

Question 30

A	The number of leaf nodes in the tree
B	The number of nodes in the tree
C	The number of internal nodes in the tree
D	The height of the tree

Data-Structures Binary-Trees Gate-2004

Question 30 Explanation:

→ Dosomething ( ) returns the max (height of left child + 1, height right child + 1).
→ So given that pointer to root of tree is passed to DoSomething ( ), it will return height of the tree. It is done when the height of single node is '0'.

Question 31

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)

Algorithms Binary-Trees Gate 2004-IT

Question 31 Explanation:

The above statement is actually algorithm for building a heap of an input array A.
And we know that time complexity for building the heap is O(n)

Question 32

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

A	Theory Explanation is given below.

Data-Structures Binary-Trees Gate-2002

Question 32 Explanation:

Total 5 binary trees are possible with the preorder C, B, A.

Question 33

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

A	(1 2 (4 5 6 7))
B	(1 (2 3 4) 5 6) 7)
C	(1 (2 3 4) (5 6 7))
D	(1 (2 3 NULL) (4 5))

Data-Structures Binary-Trees Gate-2000

Question 33 Explanation:

Option C:

(Proper Representation)

Question 34

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

A	LASTIN = LASTPOST
B	LASTIN = LASTPRE
C	LASTPRE = LASTPOST
D	None of the above

Data-Structures Binary-Trees Gate-2000

Question 34 Explanation:

In full Binary tree LASTIN = LASTPRE.
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.

Question 35

Which of the following statements is false?

A	A tree with a n nodes has (n – 1) edges
B	A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results
C	A complete binary tree with n internal nodes has (n + 1) leaves
D	Both B and C

Data-Structures Binary-Trees Gate-1998

Question 35 Explanation:

A: Tree with n nodes must have (n-1) edges.
D: The maximum no. of nodes in a binary tree of height h is 2^h+1 - 1.
h=2 ⇒ 2³ - 1 ⇒ 7

Question 36

A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

A	5 3 1 2 4 7 8 6
B	5 3 1 2 6 4 8 7
C	5 3 2 4 1 6 7 8
D	5 3 1 2 4 7 6 8

Data-Structures Binary-Trees Gate-1997

Question 36 Explanation:

Preorder traversal means (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.

Question 37

A	1
B	3
C	7
D	8

Data-Structures Binary-Trees Gate-1996

Question 37 Explanation:

a, b, c are going to unbalance.

Question 38

Which of the following sequences denotes the post order traversal sequence of the tree of question 14?

A	f e g c d b a
B	g c b d a f e
C	g c d b f e a
D	f e d g c b a

Data-Structures Binary-Trees Gate-1996

Question 38 Explanation:

Postorder:-
Left → Right → Root
g c d b f e a

Question 39

A	(4, 7)
B	(7, 4)
C	(8, 3)
D	(3, 8)

Data-Structures Binary-Trees Gate-1996

Question 39 Explanation:

50 is the root node in BST.
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).

Question 40

144

Algorithms Binary-Trees Gate-1991

Question 40 Explanation:

Question 41

A	Equal to the number of ways of multiplying (n+1) matrices.
B	Equal to the number of ways of arranging n out of 2n distinct elements.
C
D	Equal to n!.
E	Both (A) and (C).

Data-Structures Binary-Trees Gate-1990

Question 41 Explanation:

No. of rooted binary trees (unlabeled) with n nodes is given by n^th catalan number which equals (²ⁿC_n)/(n+1)
Here, both options A and C are true as option A corresponds to n multiply operations of (n+1) matrices, the no. of ways for this is again given by the n^th catalan number.

Question 42

A	≤ n² always.
B	≥ nlog₂ n always.
C	Equal to n² always.
D	O(n) for some special trees.

Data-Structures Binary-Trees Gate-1990

Question 42 Explanation:

Here the question asked for binary tree.
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × logn
But for skewed tree it will be O(n) only.
So, answer will be (D).

Question 43

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?

A	True
B	False

Data-Structures Binary-Trees GATE-1987

Question 43 Explanation:

To construct binary tree uniquely we need either inorder and postorder or inorder and preorder.

Question 44

If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.

A	True
B	False

Data-Structures Binary-Trees GATE-1987

Question 44 Explanation:

In the above binary tree, no. of leaves is 3, which is not the power of 2. Hence the given statement is false.

There are 44 questions to complete.