Data Structures Trees and Binary Search Trees 2

Question 1

How do you find the kth smallest element in a BST efficiently?

Accepted Answer

In-order traversal counting nodes until the kth is reached

Answer

Since in-order traversal of a BST yields sorted order, counting nodes during traversal and stopping at the kth gives the kth smallest in O(h+k) time.

Question 2

What is the time complexity of AVL tree insertion including rebalancing?

Accepted Answer

O(log n)

Answer

AVL insertion follows the BST insert path in O(log n) time, and rebalancing via rotations also takes O(log n) since the tree height is O(log n).

Question 3

Which traversal is used to create a copy of a binary tree?

Accepted Answer

Pre-order

Answer

Pre-order traversal visits the root before children, making it natural to recreate a tree by creating each node before its subtrees.

Question 4

What rotation operation is performed to fix a left-left imbalance in an AVL tree?

Accepted Answer

Right rotation

Answer

A left-left imbalance is corrected by a single right rotation around the unbalanced node, restoring AVL balance properties.

Question 5

What is a threaded binary tree?

Accepted Answer

A tree where null pointers are replaced with pointers to in-order successor/predecessor

Answer

A threaded binary tree replaces null left/right pointers with pointers to in-order predecessor/successor, enabling traversal without recursion or a stack.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Trees and Binary Search Trees 2