#1806·JavaScript

[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).

### Additional information Additional Information – Illustration Key Points about Morris Traversal: Memory Efficient: Uses O(1) extra space, unlike recursion or stack. Inorder Traversal: Left → Root → Right. Temporary Tree Modification: Creates “threads” to revisit nodes. Future Extension: Preorder Morris Traversal is possible with minor changes. Reference: Wikipedia → Threaded binary tree / Morris Traversal. Conceptual Analogy: Normal Traversal (Stack/Recursion) → Carrying bags for each level Morris Traversal → Using built-in tree connections temporarily, no bags Threaded Tree → Installing permanent pathways for future traversals

Source: TheAlgorithms/JavaScript