Oct 3, 2025 · Oct 3, 2025
diff --git a/Trees/MorrisTraversal.js b/Trees/MorrisTraversal.js
 // Morris Inorder Traversal
 // Reference: https://www.geeksforgeeks.org/dsa/inorder-tree-traversal-without-recursion-and-without-stack/

 /*
 * Author: Saad Arqam
 * Morris Inorder Traversal Algorithm implementation in JavaScript
 *
 * Morris Traversal is a tree traversal algorithm that allows
 * inorder traversal without using recursion or a stack.
 * It achieves O(1) extra space by temporarily modifying
 * the tree structure (creating and removing "threads").
 *
 * Reference:
 * https://en.wikipedia.org/wiki/Threaded_binary_tree#Morris_traversal
 */

 // Node class
 export class Node {
  constructor(val) {
    this.val = val
    this.left = null
    this.right = null
  }
 }

 // Morris Inorder Traversal function
 export function morrisTraversal(node) {
  const result = []
  let curr = node

  while (curr !== null) {
    if (curr.left === null) {
      result.push(curr.val)
      curr = curr.right
    } else {
      let predecessor = curr.left
      while (predecessor.right !== null && predecessor.right !== curr) {
        predecessor = predecessor.right
      }
      if (predecessor.right === null) {
        predecessor.right = curr
        curr = curr.left
      } else {
        predecessor.right = null
        result.push(curr.val)
        curr = curr.right
      }
    }
  }

  return result
 }

 // Example Tree:
 //     7
 //    / \
 //   5   8
 //  / \
 // 3   6
 //      \
 //       9
 //
 // Morris inorder traversal: [3, 5, 6, 9, 7, 8]
diff --git a/Trees/MorrisTraversal.test.js b/Trees/MorrisTraversal.test.js
 import { describe, it, expect } from 'vitest'
 import { Node, morrisTraversal } from './MorrisTraversal.js'

 describe('Morris Inorder Traversal', () => {
  it('should return inorder traversal for a binary tree', () => {
    // Tree:
    //      4
    //     / \
    //    2   5
    //   / \
    //  1   3
    const root = new Node(4)
    root.left = new Node(2)
    root.right = new Node(5)
    root.left.left = new Node(1)
    root.left.right = new Node(3)

    const result = morrisTraversal(root)
    expect(result).toEqual([1, 2, 3, 4, 5])
  })

  it('should return empty array for null input', () => {
    const result = morrisTraversal(null)
    expect(result).toEqual([])
  })

  it('should handle larger tree', () => {
    // Tree:
    //      7
    //     / \
    //    5   8
    //   / \
    //  3   6
    //       \
    //        9
    const root = new Node(7)
    root.left = new Node(5)
    root.right = new Node(8)
    root.left.left = new Node(3)
    root.left.right = new Node(6)
    root.left.right.right = new Node(9)

    const result = morrisTraversal(root)
    expect(result).toEqual([3, 5, 6, 9, 7, 8])
  })
 })
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,63 @@
		// Morris Inorder Traversal
		// Reference: https://www.geeksforgeeks.org/dsa/inorder-tree-traversal-without-recursion-and-without-stack/

		/*
		* Author: Saad Arqam
		* Morris Inorder Traversal Algorithm implementation in JavaScript
		*
		* Morris Traversal is a tree traversal algorithm that allows
		* inorder traversal without using recursion or a stack.
		* It achieves O(1) extra space by temporarily modifying
		* the tree structure (creating and removing "threads").
		*
		* Reference:
		* https://en.wikipedia.org/wiki/Threaded_binary_tree#Morris_traversal
		*/

		// Node class
		export class Node {
		constructor(val) {
		this.val = val
		this.left = null
		this.right = null
		}
		}

		// Morris Inorder Traversal function
		export function morrisTraversal(node) {
		const result = []
		let curr = node

		while (curr !== null) {
		if (curr.left === null) {
		result.push(curr.val)
		curr = curr.right
		} else {
		let predecessor = curr.left
		while (predecessor.right !== null && predecessor.right !== curr) {
		predecessor = predecessor.right
		}
		if (predecessor.right === null) {
		predecessor.right = curr
		curr = curr.left
		} else {
		predecessor.right = null
		result.push(curr.val)
		curr = curr.right
		}
		}
		}

		return result
		}

		// Example Tree:
		// 7
		// / \
		// 5 8
		// / \
		// 3 6
		// \
		// 9
		//
		// Morris inorder traversal: [3, 5, 6, 9, 7, 8]
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,46 @@
		import { describe, it, expect } from 'vitest'
		import { Node, morrisTraversal } from './MorrisTraversal.js'

		describe('Morris Inorder Traversal', () => {
		it('should return inorder traversal for a binary tree', () => {
		// Tree:
		// 4
		// / \
		// 2 5
		// / \
		// 1 3
		const root = new Node(4)
		root.left = new Node(2)
		root.right = new Node(5)
		root.left.left = new Node(1)
		root.left.right = new Node(3)

		const result = morrisTraversal(root)
		expect(result).toEqual([1, 2, 3, 4, 5])
		})

		it('should return empty array for null input', () => {
		const result = morrisTraversal(null)
		expect(result).toEqual([])
		})

		it('should handle larger tree', () => {
		// Tree:
		// 7
		// / \
		// 5 8
		// / \
		// 3 6
		// \
		// 9
		const root = new Node(7)
		root.left = new Node(5)
		root.right = new Node(8)
		root.left.left = new Node(3)
		root.left.right = new Node(6)
		root.left.right.right = new Node(9)

		const result = morrisTraversal(root)
		expect(result).toEqual([3, 5, 6, 9, 7, 8])
		})
		})