Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement Morris Traversal for In-Order Traversal #659

Open
wants to merge 1 commit into
base: main
Choose a base branch
from

Conversation

AkshitMital
Copy link

Add Morris In-Order Traversal Implementation

Fixes #626

Brief description

Added a space-efficient Morris In-Order Traversal implementation to the binary tree module, providing O(1) space complexity without using recursion or a stack.

Changes

  • Implemented morris_in_order method in BinaryTreeTraversal class
  • Added C++ backend support in BinaryTreeTraversal.hpp
  • Added unit tests to verify correctness and tree structure preservation
  • Fixed trailing whitespace issues in affected files

Implementation Details

  • Uses threaded binary tree approach for constant space traversal
  • Properly restores original tree structure after traversal
  • Supports both Python and C++ backends
  • Maintains compatibility with existing traversal interface

Testing

Added test cases that verify:

  • Correct in-order traversal sequence
  • Tree structure preservation after traversal
  • Empty tree handling
  • Node parameter handling
  • Backend compatibility (Python/C++)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

feat: Morris Traversal for In-Order Traversal
1 participant