Test: Binary Search Trees- 2 - Computer Science Engineering (CSE) MCQ

# Test: Binary Search Trees- 2 - Computer Science Engineering (CSE) MCQ

Test Description

## 20 Questions MCQ Test GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Test: Binary Search Trees- 2

Test: Binary Search Trees- 2 for Computer Science Engineering (CSE) 2024 is part of GATE Computer Science Engineering(CSE) 2025 Mock Test Series preparation. The Test: Binary Search Trees- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Binary Search Trees- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Binary Search Trees- 2 below.
Solutions of Test: Binary Search Trees- 2 questions in English are available as part of our GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) & Test: Binary Search Trees- 2 solutions in Hindi for GATE Computer Science Engineering(CSE) 2025 Mock Test Series course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Binary Search Trees- 2 | 20 questions in 60 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Binary Search Trees- 2 - Question 1

### 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 Q. 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?

Detailed Solution for Test: Binary Search Trees- 2 - Question 1

Key to be searched 273:

• I) 81, 537, 102, 439, 285, 376, 305 is not correct
We cannot go to 376 from 285 as 273 is smaller than 285.
• II) 52, 97, 121, 195, 242, 381, 472 is not correct.
We cannot go to 472 from 381 as 273 is smaller than 381.
• III) 142, 248, 520, 386, 345, 270, 307 is correct

• 550, 149, 507, 395, 463, 402, 270 is not correct. We cannot go to 463 from 395 in search of 273
Test: Binary Search Trees- 2 - Question 2

### 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  Q. Which of the following statements is TRUE?

Detailed Solution for Test: Binary Search Trees- 2 - Question 2

A: I and IV are not in ascending order
B: If 439 is root, It should be 1st element in preorder
D: IV is a postorder sequence of some BST with 149 as the root, => False

 1 Crore+ students have signed up on EduRev. Have you?
Test: Binary Search Trees- 2 - Question 3

### How many distinct BSTs can be constructed with 3 distinct keys?

Detailed Solution for Test: Binary Search Trees- 2 - Question 3

2nCn/(n+1) = 6C3/4 = 5

Test: Binary Search Trees- 2 - Question 4

What is the worst case possible height of Red-Black tree? Assume base of Log as 2 in all options

Test: Binary Search Trees- 2 - Question 5

Is the following statement valid? A Red-Black Tree which is also a perfect Binary Tree can have all black nodes

Detailed Solution for Test: Binary Search Trees- 2 - Question 5

A perfect BST with all black nodes doesn't violate any of the Red-Black tree properties.

Test: Binary Search Trees- 2 - Question 6

Which of the following operations are used by Red-Black trees to maintain balance during insertion/deletion?
a) Recoloring of nodes
b) Rotation (Left and Right)

Detailed Solution for Test: Binary Search Trees- 2 - Question 6

Both recoloring and rotation operations are used during insertion and deletion.

Test: Binary Search Trees- 2 - Question 7

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is

Detailed Solution for Test: Binary Search Trees- 2 - Question 7

The recurrence relation for the recursive function is T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
= 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^i) + (2*i - 1) * (n/2)
Where i = lg(N)
= lg((2n - 1) / 2)
O(c * T(N / 2^i) + (2*i - 1) * (n/2)) reduces to
O((2*i - 1) * (n/2))
O((2*( lg((2n - 1) / 2)) - 1) * (n/2)) ...sub the value of i.
O(n * ln(n))

Test: Binary Search Trees- 2 - Question 8

Which of the following is TRUE?

Detailed Solution for Test: Binary Search Trees- 2 - Question 8

AVL tree is a balanced tree.
AVL tree's time complexity of searching = θ(logn)
But a binary search tree, may be skewed tree, so in worst case BST searching time = θ(n)

Test: Binary Search Trees- 2 - Question 9

Given two Balanced binary search trees, B1 having n elements and B2 having m elements, what is the time complexity of the best known algorithm to merge these trees to form another balanced binary tree containing m+n elements ?

Detailed Solution for Test: Binary Search Trees- 2 - Question 9

O(m+n) as we can first perform inorder on both the trees and store them in two separate arrays. Now we have two sorted sequences and we can merge them in O(m+n) using standard merge algorithm and on the final sorted array we can use the binary search to create the tree using Recursion. Recursively adding middle element at the root and repeating the same process for left and right subarrays.

Test: Binary Search Trees- 2 - Question 10

The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is

Detailed Solution for Test: Binary Search Trees- 2 - Question 10

Time taken to search an element is where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be which is Which is] which can be written as.

Test: Binary Search Trees- 2 - Question 11

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

Detailed Solution for Test: Binary Search Trees- 2 - Question 11

AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees Following is the most unbalanced AVL tree that we can get with 7 nodes

Test: Binary Search Trees- 2 - Question 12

What is the worst case possible height of AVL tree?

Test: Binary Search Trees- 2 - Question 13

Which of the following is AVL Tree?

Detailed Solution for Test: Binary Search Trees- 2 - Question 13

A Binary Search Tree is AVL if balance factor of every node is either -1 or 0 or 1. Balance factor of a node X is [(height of X->left) - (height of X->right)]. In Tree B, the node with value 50 has balance factor 2. That is why B is not an AVL tree.

Test: Binary Search Trees- 2 - Question 14

Consider the following AVL tree.

Q. Which of the following is updated AVL tree after insertion of 70

Detailed Solution for Test: Binary Search Trees- 2 - Question 14

Refer following for steps used in AVL insertion. AVL Tree | Set 1 (Insertion)

After insertion of 70, tree becomes following

We start from 50 and travel up. We keep travelling up till we find an unbalanced node. In above case, we reach the node 60 and see 60 got unbalanced after insertion and this is Right Left Case. So we need to apply two rotations

Test: Binary Search Trees- 2 - Question 15

Which of the following is a self-adjusting or self-balancing Binary Search Tree

Detailed Solution for Test: Binary Search Trees- 2 - Question 15

See Splay Tree, AVL Tree and Red Black Tree

Test: Binary Search Trees- 2 - Question 16

Consider the following left-rotate and right-rotate functions commonly used in self-adjusting BSTs

Q.
Which of the following is tightest upper bound for left-rotate and right-rotate operations.

Detailed Solution for Test: Binary Search Trees- 2 - Question 16

The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Following are C implementations of left-rotate and right-rotate 1

Test: Binary Search Trees- 2 - Question 17

Which of the following is true

Detailed Solution for Test: Binary Search Trees- 2 - Question 17

Red Black Tree with n nodes has height <= 2Log2(n+1) AVL Tree with n nodes has height less than Logφ(√5(n+2)) - 2. Therefore, the AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree.

Test: Binary Search Trees- 2 - Question 18

Which of the following is true about Red Black Trees?

Test: Binary Search Trees- 2 - Question 19

Which of the following is true about AVL and Red Black Trees?

Detailed Solution for Test: Binary Search Trees- 2 - Question 19

Refer Red Black Tree Insertion and AVL Tree Insertion

Test: Binary Search Trees- 2 - Question 20

The number of edges from the root to the node is called __________ of the tree.

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests
Information about Test: Binary Search Trees- 2 Page
In this test you can find the Exam questions for Test: Binary Search Trees- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Binary Search Trees- 2, EduRev gives you an ample number of Online tests for practice

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests