Bachelor of Computer Engineering Data Structure Flashcards

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

Answer: In-order

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

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

Answer: O(n)

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

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

Answer: Binary heap

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

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

Answer: Each node is greater than or equal to its children

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

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

Answer: O(n)

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

Which graph traversal algorithm uses a queue to explore nodes level by level?

Answer: Breadth-First Search

BFS uses a queue (FIFO) to visit all neighbors of a node before moving to the next depth level.

What is the space complexity of Depth-First Search on a graph with V vertices and E edges?

Answer: O(V)

DFS uses a stack (or recursion stack) that holds at most V vertices in the worst case.