pydatastructs icon indicating copy to clipboard operation
pydatastructs copied to clipboard

feat: Add Morris In-Order Traversal to BinaryTreeTraversal

Open asmit27rai opened this issue 1 year ago • 0 comments

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

  1. C++ Backend:

    • Implemented the morris_in_order_traversal method in the C++ backend.
    • Exposed the method to Python using PyMethodDef.
  2. Python Binding:

    • Updated the Python binding to include the morris_in_order_traversal method.
  3. Unit Tests:

    • Added unit tests for Morris Traversal in the test suite.
    • Verified compatibility with both Python and C++ backends.

asmit27rai avatar Mar 11 '25 00:03 asmit27rai