Data Structures · Search trees and balanced trees
Let T be a BST whose nodes contain only key, left, and right fields (no parent…
Problem
Let \(T\) be a BST whose nodes contain only \(\mathrm{key}\), \(\mathrm{left}\), and \(\mathrm{right}\) fields (no parent pointers, no sizes). Design a single-pass algorithm that returns the \(k\)-th smallest key for a given \(k\) with \(1 \le k \le n\), using \(O(h)\) extra memory. You may use recursion or an explicit stack. Prove that your algorithm visits \(O(h + k)\) nodes in the worst case, and exhibit a family of BSTs and a choice of \(k\) showing that \(\Omega(h + k)\) nodes must be visited by any algorithm that only walks tree edges and has no extra augmenting fields.
Hint
Without sizes you cannot jump into the middle of a subtree. Inorder already names the \(k\)th key as the \(k\)th key it emits; stop there.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Data Structures sample problem: Try the free sample problem.
More Data Structures practice problems
- Let V be a dynamic array of n elements stored in a buffer of capacity c, with the…Abstract data types, representation, and invariants
- A ring buffer (circular array) of fixed capacity C≥ 1 stores a sequence of at most C…Abstract data types, representation, and invariants
- Let L be the doubly linked list with values [10, 20, 30, 40, 50], and let I be a…Arrays, linked structures, stacks, queues, and amortization
- Consider BST deletion of a node zSearch trees and balanced trees
- Consider a hash table T of size m = 11 that resolves collisions by chainingHash tables and probabilistic performance
- Throw n balls independently and uniformly into n binsHash tables and probabilistic performance
- `Bubble-Down`(A,i,n) is specified as follows on a 1-based array that is a complete…Heaps, priority queues, and disjoint sets
- The fat-node method of partial persistence stores, in each field of each node, a…Graph representations and traversals
- A duplicate minimum must sit on the min-stack, or one pop forgets the otherArrays, linked structures, stacks, queues, and amortization