Data Structures Trees and Binary Search Trees 2 — Questions and Answers
Question 1: How do you find the kth smallest element in a BST efficiently?
- Sort all elements then index
- In-order traversal counting nodes until the kth is reached (Correct answer)
- Use a max-heap of size k
- Level-order traversal and sort
Correct answer: In-order traversal counting nodes until the kth is reached
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?
- O(1)
- O(log n) (Correct answer)
- O(n)
- O(n log n)
Correct answer: O(log n)
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?
- In-order
- Post-order
- Level-order
- Pre-order (Correct answer)
Correct answer: Pre-order
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?
- Left rotation
- Right rotation (Correct answer)
- Left-right double rotation
- Right-left double rotation
Correct answer: Right rotation
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?
- A tree where each node stores a thread ID
- A tree where null pointers are replaced with pointers to in-order successor/predecessor (Correct answer)
- A tree used for concurrent access
- A tree where all nodes are connected in a circular manner
Correct answer: A tree where null pointers are replaced with pointers to in-order successor/predecessor
A threaded binary tree replaces null left/right pointers with pointers to in-order predecessor/successor, enabling traversal without recursion or a stack.
Question 6: What does it mean for a binary tree to be height-balanced?
- Both subtrees have the same number of nodes
- The height difference between left and right subtrees is at most 1 for every node (Correct answer)
- The tree is a complete binary tree
- All leaf nodes are at the same level
Correct answer: The height difference between left and right subtrees is at most 1 for every node
A height-balanced tree (like AVL) requires that the heights of left and right subtrees differ by no more than 1 at every node, not just the root.
Data Structures Trees and Binary Search Trees 2
How do you find the kth smallest element in a BST efficiently?