Mark and Compact a Heap-Indexed Subtree
A memory manager stores a binary tree in an array: the node at index i has children at 2i+1 and 2i+2; a null slot means no node (and thus no subtree below it). Implement the GC operation markAndCompact(heapArray, k):
Mark the entire subtree rooted at index k as garbage, then compact the surviving values to the front of a new array, preserving their original order, and return [newArray, remap] where remap maps old index to new index for every survivor (references into the array must be patched — that is the remap's job). An out-of-range k, or a k pointing at a null slot, marks nothing — but compaction still drops the null slots.
markAndCompact(["A","B","C","D","E","F","G"], 1)
-> [["A","C","F","G"], {0: 0, 2: 1, 5: 2, 6: 3}]Hints
Hint 1
Phase one, mark: walk the implicit tree from k with an explicit stack (children 2i+1 and 2i+2), stopping at out-of-range indices and null slots — a null slot prunes its whole implicit subtree.
Hint 2
Phase two, compact: one left-to-right pass copying every non-null unmarked value, recording old -> new in the remap as you go. Voicing why the remap must be returned (compaction breaks the implicit indexing) is the design point.