4 ms·
Why wouldn't you do a pre-order traversal and connect the appropriate nodes? When they say "recursion is key", that's actually misleading and this problem doesn
by mrburton 8y ago
Why wouldn't you do a pre-order traversal and connect the appropriate nodes? When they say "recursion is key", that's actually misleading and this problem doesn't seem hard at all.
What am I missing?
- panarky 8y ago>> The operation can be done in O(n) time -- essentially operating on each node once. > Why wouldn't you do a pre-order traversal Because then it wouldn't be O(n)
- sqd 8y agoI can surely do a pre-order DFS and record the order of the nodes I visited, and then another DFS to modify the pointers? That would still be O(n).
- mwkaufma 8y agoThe 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.