3 ms·
>> 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
by 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).