[FEATURE]: Add Morris Traversal Algorithm
Author: aniket866Created Sep 29, 2025Updated Oct 4, 2025
### Motivation
> ### Describe your change:
>
> * [x] Add an algorithm?
> * [ ] Fix a bug or typo in an existing algorithm?
> * [ ] Documentation change?
>
> ### Checklist:
>
> * [x] I have read [[CONTRIBUTING.md](https://github.com/TheAlgorithms/Javascript/blob/master/CONTRIBUTING.md)](https://github.com/TheAlgorithms/Javascript/blob/master/CONTRIBUTING.md).
> * [x] This pull request is all my own work -- I have not plagiarized.
> * [x] I know that pull requests will not be merged if they fail the automated tests.
> * [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
> * [x] All new JavaScript files are placed inside an existing directory.
> * [x] All filenames should use the UpperCamelCase (PascalCase) style. There should be no spaces in filenames.
> **Example:** `UserProfile.js` is allowed but `userprofile.js`,`Userprofile.js`,`user-Profile.js`,`userProfile.js` are not.
> * [x] All new algorithms have a URL in their comments that points to Wikipedia or another similar explanation.
> **Example:** [[Morris Traversal - Wikipedia](https://en.wikipedia.org/wiki/Threaded_binary_tree#Morris_traversal)](https://en.wikipedia.org/wiki/Threaded_binary_tree#Morris_traversal)
> * [ ] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.
> * [ ] closes
### Examples
7
/ \
5 8
/ \
3 6
\
9
Traversal order (Inorder: Left → Root → Right):
Step 1: Visit leftmost node → 3
Step 2: Back to parent → 5
Step 3: Move to right subtree → 6
Step 4: Right child of 6 → 9
Step 5: Back to root → 7
Step 6: Right child of root → 8
Final output sequence:
3, 5, 6, 9, 7, 8
### Possible workarounds
Possible Workarounds – Conceptual Illustration
Method | Space Complexity | Notes
-- | -- | --
Recursive Inorder Traversal | O(h) | Uses call stack; simple but not O(1)
Iterative Inorder with Stack | O(h) | Explicit stack; simulates recursion
Threaded Binary Tree | O(1) | Permanently modifies tree pointers for threads
Visual analogy:
-
Recursive / Stack → climbing stairs with a backpack (stack grows with height).
-
Morris Traversal → climbing stairs using only your hands on rails (no extra backpack).
-
Threaded Tree → installing permanent rails on stairs (extra setup, but efficient traversal).
Source: TheAlgorithms/JavaScript