Saturday, August 7, 2010

Implement a tree visit with no recursion and no stack

Interesting approach here. Visit of the tree obviously just requires O(1) memory. So why we keep teaching it with a stack or by using recursion?

1 comment:

  1. I was taught both at school.
    Using the runtime stack has several advantages though: it's typically faster, it's easier to write, and it works for any recursive structure (think containers of containers), without the need to add parent pointers.

    ReplyDelete