pydatastructs
pydatastructs copied to clipboard
feat: Add Morris In-Order Traversal to BinaryTreeTraversal
Description
This PR adds the Morris In-Order Traversal algorithm to the BinaryTreeTraversal class. 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.
Changes
-
C++ Backend:
- Implemented the
morris_in_order_traversalmethod in the C++ backend. - Exposed the method to Python using
PyMethodDef.
- Implemented the
-
Python Binding:
- Updated the Python binding to include the
morris_in_order_traversalmethod.
- Updated the Python binding to include the
-
Unit Tests:
- Added unit tests for Morris Traversal in the test suite.
- Verified compatibility with both Python and C++ backends.