Is it possible to do a tree traversal/flattening tree process in O(1) space? (Morris Traversal)

Questions / Help
1

I just came across a concept called Morris Traversal which is a tree traversal algorithm that does not employ the use of recursion or a stack. The advantage of this is that the space complexity is reduced to O(1) compared to the normal solutions.

I basically came across this solution when I was trying to solve the Flatten Binary Tree to Linked List problem and was really impressed by the given solution.

Is something like this possible to perform in Elixir?

2

There is no magic here. The complexity is just shifted to building and maintaining a threaded binary tree. I don’t see a reason why this couldn’t be done in Elixir.

3

But without recursion you’d need some mutable data structure like an Agent for example.

4

You’re right, I missed the part about avoiding recursion!

5

Just asking. Wouldn’t implementing this using recursion be difficult too since according to the solution here, we update both the right value of a pointer called root and then shortly afterwards the root pointer itself.

For example, a short snippet of what I’m saying:

if(root.left){
     root.right = root.left;
}
root = root.right;

Isn’t this impossible due to the immutability nature of Elixir?

6

Do you have a good description at hand how the algorithm works?
… with pictures please :grin: