Hacker News Reader

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?

View on HN

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.

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

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

Reply on news.ycombinator.com