1

Well I know there is a post out there from '09, but I'm still not sure how to implement this. I didn't understand the solution that Anton gave here, also it is very old thread: Iterating over a Binary Tree with O(1) Auxiliary Space

Thus, I hope after 8 years we can think of some other solutions, any help is much appreciated.

Note: It was an interview question for my friend, the hint was always knowing where we came from.

Ilan Aizelman WS
  • 1,630
  • 2
  • 21
  • 44
  • IMHO the answer in the linked post is cheating. Instead of keeping the memory in a stack (auxiliary or recursion), the author of the answer kelt it as an additional field in node. Another field to each node is O(n) space... As far as I know, you cannot traverse a binary with O(1) space without destroying the tree (as suggested in another answer) – Ginandi Jun 03 '17 at 14:26
  • 1
    "Thus, I hope after 8 years we can think of some other solutions", you will be surprise but no. We still waiting "The Art of Computer Programming 4B" :p. – Stargateur Jun 03 '17 at 14:26
  • @Stargateur haha that's a good one. – Ilan Aizelman WS Jun 03 '17 at 14:32

0 Answers0