codezonediitj
feat: Morris Traversal for In-Order Traversal
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
- Implement Morris Traversal for in-order traversal.
- Add unit tests to verify the correctness of the implementation.
References
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.
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.
Hello @asmit27rai, I have submitted a pull request for your review. Please let me know your thoughts.