B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 2

Question 1

Which tree traversal visits nodes in the order: left subtree, root, right subtree?

Accepted Answer

In-order

Answer

In-order traversal visits left subtree first, then the root, then the right subtree, yielding sorted output for a BST.

Question 2

What is the worst-case time complexity for searching in an unbalanced Binary Search Tree with n nodes?

Accepted Answer

O(n)

Answer

In the worst case, a BST degrades to a linked list (e.g., sorted insertions), making search O(n).

Question 3

Which data structure is most appropriate for implementing a priority queue efficiently?

Accepted Answer

Binary heap

Answer

A binary heap supports O(log n) insert and O(log n) extract-min/max, making it ideal for priority queues.

Question 4

In a max-heap, which property must hold for every node?

Accepted Answer

Each node is greater than or equal to its children

Answer

The max-heap property requires every parent node to be greater than or equal to its children.

Question 5

What is the time complexity of building a heap from an unsorted array of n elements using the heapify approach?

Accepted Answer

O(n)

Answer

Bottom-up heap construction using heapify runs in O(n) due to the mathematical sum of subtree heights.

B CompE Bachelor of Computer Engineering Practice Test