4 ms·
The spirit of the problem, as it was presented to us in undergrad, is to modify the data structure in-place, not by allocating a scratch array.
by mwkaufma 8y ago
The spirit of the problem, as it was presented to us in undergrad, is to modify the data structure in-place, not by allocating a scratch array.
- benmmurphy 8y agoI think if you place a limit on O(log(n)) space being allocated and guarantee the height of the tree is at most O(log(n)) then it breaks the scratch solution and makes the inplace solution where you use scratch on the stack the only solution. probably the inplace solution can be fixed to use O(log(n)) space even if it the tree is unbalanced because you don't need to allocate stack space unless a node has both a left and a right pointer.