Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Add morris traversal algorithm#1810

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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
PARTH-TUSSLE wants to merge2 commits intoTheAlgorithms:master
base:master
Choose a base branch
Loading
fromPARTH-TUSSLE:add-morris-traversal-algorithm
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
110 changes: 110 additions & 0 deletionsTrees/MorrisTraversal.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
/**
* Morris Traversal (Inorder Traversal without recursion or stack)
* Wikipedia: https://en.wikipedia.org/wiki/Threaded_binary_tree#Morris_traversal
*
* WHAT IS MORRIS TRAVERSAL?
* Morris Traversal is a clever technique to traverse a binary tree in inorder
* (Left → Root → Right) using O(1) extra space - meaning it doesn't need recursion
* or an explicit stack like traditional methods.
*
* HOW DOES IT WORK?
* The algorithm temporarily modifies the tree by creating "threads" (temporary links)
* that help us navigate back to parent nodes without using extra memory.
* Think of it like leaving breadcrumbs to find your way back!
*
* KEY CONCEPT - INORDER PREDECESSOR:
* For any node, its inorder predecessor is the rightmost node in its left subtree.
* This is the node that comes just before it in inorder traversal.
*
* ALGORITHM STEPS:
* 1. Start at root, move current pointer through the tree
* 2. If current node has no left child: visit it, move right
* 3. If current node has left child:
* a. Find the inorder predecessor (rightmost in left subtree)
* b. If predecessor's right is null: create thread, go left
* c. If predecessor's right points to current: remove thread, visit current, go right
*
* Example Tree:
* 7
* / \
* 5 8
* / \
* 3 6
* \
* 9
*
* Traversal order: 3 → 5 → 6 → 9 → 7 → 8
*
* TIME COMPLEXITY: O(n) - each edge is traversed at most twice
* SPACE COMPLEXITY: O(1) - no extra space except for result array
*/

class TreeNode {
constructor(val, left = null, right = null) {
this.val = val
this.left = left
this.right = right
}
}

function morrisTraversal(root) {
const result = [] // Array to store the inorder traversal result

// Handle edge case: empty tree
if (!root) {
return result
}

let curr = root // Current node we're processing

// Continue until we've processed all nodes
while (curr) {
// CASE 1: Current node has no left child
// This means we can safely visit this node (no left subtree to process first)
if (!curr.left) {
result.push(curr.val) // Visit the current node
curr = curr.right // Move to right subtree
}

// CASE 2: Current node has a left child
// We need to find a way to come back to this node after processing left subtree
else {
// STEP 1: Find the inorder predecessor of current node
// (Rightmost node in the left subtree)
let pred = curr.left

// Keep going right until we find the rightmost node
// BUT stop if we find a node that already points back to curr (existing thread)
while (pred.right && pred.right !== curr) {
pred = pred.right
}

// STEP 2a: If predecessor's right is null, we need to create a thread
// This thread will help us return to current node later
if (!pred.right) {
// Create the thread: make predecessor point to current node
pred.right = curr

// Now go left to process the left subtree first
curr = curr.left
}

// STEP 2b: If predecessor's right already points to current node
// This means we've already processed the left subtree and are back via the thread
else {
// Remove the thread (restore original tree structure)
pred.right = null

// Now we can safely visit the current node
result.push(curr.val)

// Move to right subtree
curr = curr.right
}
}
}

return result
}

export { TreeNode, morrisTraversal }
96 changes: 96 additions & 0 deletionsTrees/test/MorrisTraversal.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
import { TreeNode, morrisTraversal } from '../MorrisTraversal'

describe('Morris Traversal', () => {
it('Empty tree case', () => {
expect(morrisTraversal(null)).toStrictEqual([])
})

it('Single node tree', () => {
const root = new TreeNode(42)
expect(morrisTraversal(root)).toStrictEqual([42])
})

it('Simple inorder traversal', () => {
// Tree structure:
// 2
// / \
// 1 3
const root = new TreeNode(2, new TreeNode(1), new TreeNode(3))
expect(morrisTraversal(root)).toStrictEqual([1, 2, 3])
})

it('Complex tree traversal - Example from documentation', () => {
// Tree structure:
// 7
// / \
// 5 8
// / \
// 3 6
// \
// 9
const root = new TreeNode(
7,
new TreeNode(5, new TreeNode(3), new TreeNode(6, null, new TreeNode(9))),
new TreeNode(8)
)
expect(morrisTraversal(root)).toStrictEqual([3, 5, 6, 9, 7, 8])
})

it('Left skewed tree', () => {
// Tree structure:
// 3
// /
// 2
// /
// 1
const root = new TreeNode(3, new TreeNode(2, new TreeNode(1)))
expect(morrisTraversal(root)).toStrictEqual([1, 2, 3])
})

it('Right skewed tree', () => {
// Tree structure:
// 1
// \
// 2
// \
// 3
const root = new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3)))
expect(morrisTraversal(root)).toStrictEqual([1, 2, 3])
})

it('Larger tree with mixed structure', () => {
// Tree structure:
// 10
// / \
// 5 15
// / \ \
// 3 7 18
// / / \
// 1 6 8
const root = new TreeNode(
10,
new TreeNode(
5,
new TreeNode(3, new TreeNode(1)),
new TreeNode(7, new TreeNode(6), new TreeNode(8))
),
new TreeNode(15, null, new TreeNode(18))
)
expect(morrisTraversal(root)).toStrictEqual([1, 3, 5, 6, 7, 8, 10, 15, 18])
})

it('Tree with duplicate values', () => {
// Tree structure:
// 5
// / \
// 5 5
// / \
// 3 7
const root = new TreeNode(
5,
new TreeNode(5, new TreeNode(3)),
new TreeNode(5, null, new TreeNode(7))
)
expect(morrisTraversal(root)).toStrictEqual([3, 5, 5, 5, 7])
})
})
[8]ページ先頭
©2009-2025 Movatter.jp