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?
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.
But without recursion you’d need some mutable data structure like an Agent for example.
You’re right, I missed the part about avoiding recursion!
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:
root.right = root.left;
root = root.right;
Isn’t this impossible due to the immutability nature of Elixir?
Do you have a good description at hand how the algorithm works?
… with pictures please