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.