Hacker News Reader

>> 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)

I 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).