Morris Traversal Inorder Without Stack in DSA Javascript - Build from Scratch

Morris Traversal Inorder Without Stack

📖 Scenario: You are working with a binary tree data structure. Normally, to visit nodes in order (left, root, right), you use a stack or recursion. But here, you want to do it without extra memory, using a clever method called Morris Traversal.This method temporarily changes the tree links to remember where to go next, then restores the tree after visiting.

🎯 Goal: Build a JavaScript program that performs an inorder traversal of a binary tree using Morris Traversal technique without using a stack or recursion. The program should print the node values in inorder sequence.

📋 What You'll Learn

Create a binary tree with the exact structure given

Add a variable to hold the current node during traversal

Implement Morris Traversal inorder logic without stack or recursion

Print the inorder traversal result as a sequence of node values separated by spaces

💡 Why This Matters

🌍 Real World

Morris Traversal is useful in systems with limited memory where recursion or stack usage is costly, such as embedded systems or large tree processing.

💼 Career

Understanding Morris Traversal shows mastery of tree traversal algorithms and memory optimization, valuable for software engineers working on performance-critical applications.

1

Create the binary tree nodes

Create a binary tree with nodes using the Node class. Build this exact tree structure:
4
/ \
2 5
/ \
1 3
Use the Node constructor to create nodes with values 4, 2, 5, 1, and 3. Connect them to form the tree as shown.

DSA Javascript

// Define Node class and create nodes to form the tree
// Your code here

Hint

Define a Node class with val, left, and right properties. Then create nodes and link them as shown.

2

Initialize the current node variable

Create a variable called current and set it to the root node root. This variable will track the node you are currently visiting during traversal.

DSA Javascript

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

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);

// Initialize current node to root
// Your code here

Hint

Just create a variable current and assign it the value root.

3

Implement Morris Traversal inorder logic

Write a while loop that runs while current is not null. Inside the loop, if current.left is null, print current.val and move current to current.right. Otherwise, find the inorder predecessor of current (the rightmost node in current.left subtree). If the predecessor's right is null, set it to current and move current to current.left. If the predecessor's right is current, set it back to null, print current.val, and move current to current.right. Collect the printed values in an array called result.

DSA Javascript

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

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);

let current = root;

// Implement Morris Traversal inorder logic
// Your code here

Hint

Use a while loop and follow the Morris Traversal steps carefully. Use result array to store visited node values.

4

Print the inorder traversal result

Print the contents of the result array as a single string with values separated by spaces using console.log.

DSA Javascript

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

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);

let current = root;
const result = [];

while (current !== null) {
  if (current.left === null) {
    result.push(current.val);
    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;
      result.push(current.val);
      current = current.right;
    }
  }
}

// Print the inorder traversal result
// Your code here

Hint

Use console.log(result.join(' ')) to print the values separated by spaces.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to traditional methods?

easy

A. It only works on binary search trees

B. It is faster than all other traversal methods

C. It requires a queue to store nodes

D. It uses no extra space like stack or recursion

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal modifies tree links temporarily to avoid using stack or recursion, so it uses O(1) extra space.

2. Step 2: Compare with traditional methods

   Traditional inorder traversal uses stack or recursion which requires O(h) space, where h is tree height.

3. Final Answer:

   It uses no extra space like stack or recursion -> Option D

4. Quick Check:

   Morris Traversal = O(1) space [OK]

Hint: Morris Traversal avoids stack and recursion for space savings [OK]

Common Mistakes:

• Thinking Morris Traversal is faster in time complexity
• Assuming it only works on binary search trees
• Believing it uses extra data structures like queues

2. Which of the following is the correct way to find the inorder predecessor of a node curr in Morris Traversal?

easy

A. Move to the left child of curr and then keep moving right until right child is null or curr

B. Move to the right child of curr until null

C. Move to the left child of curr only once

D. Move to the right child of curr and then keep moving left until left child is null

Solution

1. Step 1: Identify inorder predecessor in Morris Traversal

   The inorder predecessor is the rightmost node in the left subtree of curr.

2. Step 2: Traverse left subtree then rightmost path

   Start at curr.left, move right repeatedly until right child is null or points back to curr.

3. Final Answer:

   Move to the left child of curr and then keep moving right until right child is null or curr -> Option A

4. Quick Check:

   Inorder predecessor = left subtree's rightmost node [OK]

Hint: Inorder predecessor = left child then rightmost path [OK]

Common Mistakes:

• Moving right child first instead of left
• Stopping after one left move without going right
• Confusing predecessor with successor

3. What will be the output of Morris inorder traversal on the following binary tree?

    2
   / \
  1   3

Assuming the traversal prints node values in order.

medium

A. [1, 3, 2]

B. [2, 1, 3]

C. [1, 2, 3]

D. [3, 2, 1]

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then current node, then right subtree.

2. Step 2: Apply Morris traversal on given tree

   Left child is 1, root is 2, right child is 3, so output is [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Inorder = left, root, right = [1, 2, 3] [OK]

Hint: Inorder prints left, root, right nodes [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Mixing node visit order
• Assuming traversal prints in reverse

4. Consider this snippet of Morris Traversal code:

while (curr !== null) {
  if (curr.left === null) {
    console.log(curr.val);
    curr = curr.right;
  } else {
    let pred = curr.left;
    while (pred.right !== null && pred.right !== curr) {
      pred = pred.right;
    }
    if (pred.right === null) {
      pred.right = curr;
      curr = curr.left;
    } else {
      pred.right = null;
      console.log(curr.val);
      curr = curr.right;
    }
  }
}

What is the error in this code?

medium

A. It misses printing the current node after restoring links

B. It never prints the current node's value

C. It creates infinite loop by not updating curr

D. It incorrectly sets pred.right to curr.left

Solution

1. Step 1: Check when node values are printed

   Values are printed only when curr.left === null, but after restoring links, printing is missing.

2. Step 2: Identify missing print after restoring links

   After setting pred.right = null, the code moves curr = curr.right without printing curr.val.

3. Final Answer:

   It misses printing the current node after restoring links -> Option A

4. Quick Check:

   Print missing after restoring links = bug [OK]

Hint: Print node after restoring links to avoid missing values [OK]

Common Mistakes:

• Not printing node after restoring predecessor link
• Confusing when to update curr pointer
• Incorrectly modifying tree structure

5. You want to modify Morris Traversal inorder to collect node values in an array instead of printing. Which change is necessary to correctly collect all nodes in order?

hard

A. Push curr.val only when curr.left === null

B. Push curr.val both when curr.left === null and after restoring links

C. Push curr.val only after restoring links

D. Push curr.val before moving to left child

Solution

1. Step 1: Identify when nodes are visited in Morris Traversal

   Nodes are visited either when curr.left === null or after restoring the threaded link.

2. Step 2: Collect values at both visit points

   To collect all nodes in inorder, push curr.val both when curr.left === null and after restoring links (before moving right).

3. Final Answer:

   Push curr.val both when curr.left === null and after restoring links -> Option B

4. Quick Check:

   Collect values at both visits = correct inorder [OK]

Hint: Collect node values at both visits for full inorder [OK]

Common Mistakes:

• Collecting values only once misses nodes
• Collecting before moving left causes wrong order
• Ignoring second visit after restoring links