HU Binary Search Tree Questions Worksheet

Q2.11 Point
Claim: The smallest value in a BST is in the leftmost leaf.
O True
O False
Q2.2
2 Points
Consider a node, x, representing the element with rank k among n elements, in a BST.
(i.e., x is the k-th smallest). Assume k + n.
Claim: The element with rank k+1 can always be found by taking one step down and to the
right from x, and then taking as many steps as possible, down and to the left.
O True
O False
Explain in one or two lines:
Enter your answer here
Q2.3
2 Points
Consider: (i) stable Quicksort
(ii) incremental construction of a BST
Claim: (i) and (ii) are actually the same algorithm. Assume no duplicates.
O True
O False
Explain in one or two lines: