feat: Morris Traversal for In-Order Traversal

[asmit27rai]

Implement Morris Traversal for In-Order Traversal

Description

Morris Traversal is a space-efficient algorithm for performing in-order traversal of a binary tree without using recursion or a stack. It achieves O(1) space complexity by temporarily modifying the tree structure using threaded binary trees.

Tasks

1. Implement Morris Traversal for in-order traversal.
2. Add unit tests to verify the correctness of the implementation.

References

• Morris Traversal Wikipedia

[AkshitMital]

Hi @asmit27rai ,

I'm currently integrating Morris in-order traversal into our binary trees module. Given that Morris traversal is essentially a DFS variant with O(1) space, I’m debating the best design approach. Should I integrate it as an option within the existing depth_first_search method (for example, by adding an order prop value like "morris_inorder") so that it shares the DFS interface, or would it be preferable to implement it as a standalone function with separate test cases?

I'd appreciate your guidance on which approach better fits our code design and testing conventions.

[asmit27rai]

Hi @asmit27rai ,

I'm currently integrating Morris in-order traversal into our binary trees module. Given that Morris traversal is essentially a DFS variant with O(1) space, I’m debating the best design approach. Should I integrate it as an option within the existing depth_first_search method (for example, by adding an order prop value like "morris_inorder") so that it shares the DFS interface, or would it be preferable to implement it as a standalone function with separate test cases?

I'd appreciate your guidance on which approach better fits our code design and testing conventions.

Morris in-order traversal should be standalone to keep DFS clean, avoid modifying trees within shared logic, and allow targeted testing. Its unique threading mechanism makes separate implementation more readable and maintainable.

[AkshitMital]

Hello @asmit27rai, I have submitted a pull request for your review. Please let me know your thoughts.