Sep 29, 2025 · Sep 30, 2025
diff --git a/Trees/MorrisTraversal.js b/Trees/MorrisTraversal.js
 export class Node {
  constructor(data) {
    this.data = data
    this.left = null
    this.right = null
  }
 }

 export class BinaryTree {
  constructor() {
    this.root = null
  }

  morrisTraversal() {
    const traversal = []
    let current = this.root

    while (current !== null) {
      if (current.left === null) {
        traversal.push(current.data)
        current = current.right
      } else {
        let predecessor = current.left
        while (predecessor.right !== null && predecessor.right !== current) {
          predecessor = predecessor.right
        }

        if (predecessor.right === null) {
          predecessor.right = current
          current = current.left
        } else {
          predecessor.right = null
          traversal.push(current.data)
          current = current.right
        }
      }
    }

    return traversal
  }
 }
diff --git a/Trees/test/MorrisTraversal.test.js b/Trees/test/MorrisTraversal.test.js
 import { BinaryTree, Node } from '../Trees/MorrisTraversal.js'

 describe('Morris Inorder Tree Traversal', () => {
  const binaryTree = new BinaryTree()

  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)
  binaryTree.root = root

  it('Binary tree - Empty case', () => {
    const emptyTree = new BinaryTree()
    expect(emptyTree.morrisTraversal()).toStrictEqual([])
  })

  it('Binary tree - Morris inorder traversal', () => {
    const traversal = binaryTree.morrisTraversal()
    expect(traversal).toStrictEqual([3, 5, 6, 9, 7, 8])
  })
 })
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,41 @@
		export class Node {
		constructor(data) {
		this.data = data
		this.left = null
		this.right = null
		}
		}

		export class BinaryTree {
		constructor() {
		this.root = null
		}

		morrisTraversal() {
		const traversal = []
		let current = this.root

		while (current !== null) {
		if (current.left === null) {
		traversal.push(current.data)
		current = current.right
		} else {
		let predecessor = current.left
		while (predecessor.right !== null && predecessor.right !== current) {
		predecessor = predecessor.right
		}

		if (predecessor.right === null) {
		predecessor.right = current
		current = current.left
		} else {
		predecessor.right = null
		traversal.push(current.data)
		current = current.right
		}
		}
		}

		return traversal
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,23 @@
		import { BinaryTree, Node } from '../Trees/MorrisTraversal.js'

		describe('Morris Inorder Tree Traversal', () => {
		const binaryTree = new BinaryTree()

		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)
		binaryTree.root = root

		it('Binary tree - Empty case', () => {
		const emptyTree = new BinaryTree()
		expect(emptyTree.morrisTraversal()).toStrictEqual([])
		})

		it('Binary tree - Morris inorder traversal', () => {
		const traversal = binaryTree.morrisTraversal()
		expect(traversal).toStrictEqual([3, 5, 6, 9, 7, 8])
		})
		})