Consider the following binary search tree T given below. Which node contains the fourth smallest element in T?\n[Diagram: P -> L:Q, R:V. Q -> L:U, R:W. U -> R:X? V -> R:Y. W -> L:X?, R:Z. Diagram is P(Q(U, W(X, Z)), V(Y?)). The arrows are a bit distinct.]\nTree structure from visual: Root P. Left Q. Right V.\nQ has Left U, Right W.\nU has no children?\nW has Left X, Right Z.\nV has Left ?, Right Y.\nIn-order traversal (Sorted): \nSubtree Q: U, Q, X, W, Z. \nThen P.\nThen Subtree V.\nOrder: U, Q, X, W, Z, P, ...\n1st: U. 2nd: Q. 3rd: X. 4th: W.
- A. Q
- B. V
- C. W
- D. X
Answer: C. W
Explanation: In-order traversal visits nodes in non-decreasing order.\nLeftmost is U (1st).\nParent Q (2nd).\nRight child of Q is W. Left of W is X. So X (3rd).\nThen W (4th).\nThen Z (5th).