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

Morris Traversal Inorder Without Stack

📖 Scenario: You are working with a binary tree data structure. You want to visit all nodes in the tree in order (left, root, right) without using extra memory like a stack or recursion.This technique is called Morris Traversal. It temporarily changes the tree structure to remember where to go next.

🎯 Goal: Build a TypeScript program that performs Morris inorder traversal on a binary tree and prints the node values in order without using a stack or recursion.

📋 What You'll Learn

Create a binary tree node class called TreeNode with val, left, and right properties

Create a sample binary tree with exactly these nodes and structure:
Root = 1
Root.left = 2
Root.right = 3
Root.left.left = 4
Root.left.right = 5

Create a function called morrisInorderTraversal that takes the root node and prints the values in inorder using Morris Traversal

Print the node values separated by spaces on one line

💡 Why This Matters

🌍 Real World

Morris Traversal is useful in systems with limited memory where recursion or stacks are expensive, such as embedded systems or large trees.

💼 Career

Understanding tree traversal without extra memory is valuable for optimizing algorithms in software engineering and technical interviews.

1

Create the binary tree nodes

Create a class called TreeNode with a constructor that takes a number val and sets left and right to null. Then create the binary tree nodes exactly as follows:
root with value 1,
root.left with value 2,
root.right with value 3,
root.left.left with value 4,
root.left.right with value 5.

DSA Typescript

// Create TreeNode class and the binary tree nodes
// Your code here

Hint

Define the TreeNode class first. Then create root and assign its left and right children as new TreeNode instances.

2

Set up the Morris Traversal function

Create a function called morrisInorderTraversal that takes a parameter root of type TreeNode | null. Inside the function, create a variable current and set it to root.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Create morrisInorderTraversal function and set current to root
// Your code here

Hint

Define the function with the correct parameter and initialize current to root.

3

Implement the Morris Traversal logic

Inside morrisInorderTraversal, write a while loop that runs while current is not null. Inside the loop, if current.left is null, print current.val followed by a space and move current to current.right. Otherwise, find the rightmost node in current.left subtree (called predecessor). If predecessor.right is null, set it to current and move current to current.left. If predecessor.right is current, set it back to null, print current.val followed by a space, and move current to current.right.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

function morrisInorderTraversal(root: TreeNode | null): void {
    let current = root;
    // Implement Morris Traversal loop here
    // Your code here
}

Hint

Use a while loop to traverse. If no left child, print and go right. Otherwise, find predecessor and create or remove thread accordingly.

4

Run the traversal and print output

Call morrisInorderTraversal with root to print the inorder traversal of the tree.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

function morrisInorderTraversal(root: TreeNode | null): void {
    let current = root;
    while (current !== null) {
        if (current.left === null) {
            process.stdout.write(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;
                process.stdout.write(current.val + " ");
                current = current.right;
            }
        }
    }
}

// Call morrisInorderTraversal with root
// Your code here

Hint

Simply call the function with root to see the inorder traversal printed.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to the traditional recursive or stack-based methods?

easy

A. It is faster than all other traversal methods.

B. It uses no extra space for stack or recursion.

C. It only works for binary search trees.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand space usage in tree traversals

   Traditional inorder traversal uses recursion or a stack, which requires extra memory proportional to tree height.

2. Step 2: Morris Traversal space optimization

   Morris Traversal cleverly uses threaded binary trees to avoid stack or recursion, thus using O(1) extra space.

3. Final Answer:

   It uses no extra space for stack or recursion. -> Option B

4. Quick Check:

   Morris Traversal = O(1) space [OK]

Hint: Remember Morris uses tree links, no stack needed [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Believing Morris only works on BSTs
• Assuming Morris modifies tree permanently

2. Which of the following TypeScript code snippets correctly initializes the current node for Morris inorder traversal?

easy

A. let current: TreeNode | null = root;

B. let current = null;

C. let current: TreeNode = null;

D. let current: TreeNode = root.left;

Solution

1. Step 1: Identify correct initialization type

   We start traversal from the root node, so current should be root and allow null for empty trees.

2. Step 2: Check TypeScript syntax

   TypeScript requires correct type with possible null, so 'TreeNode | null' is correct.

3. Final Answer:

   let current: TreeNode | null = root; -> Option A

4. Quick Check:

   Correct type and initialization = let current: TreeNode | null = root; [OK]

Hint: Start traversal at root with nullable node type [OK]

Common Mistakes:

• Assigning null without type union
• Starting from root.left instead of root
• Using uninitialized or wrong type

3. Consider the following TypeScript code for Morris inorder traversal on this tree:

    2
   / \
  1   3

What will be the printed output sequence?

medium

A. [3, 2, 1]

B. [2, 1, 3]

C. [1, 2, 3]

D. [1, 3, 2]

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then node, then right subtree. For this tree, order is 1, 2, 3.

2. Step 2: Morris traversal mimics inorder without stack

   Morris traversal outputs nodes in inorder sequence, so output will be [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Inorder of given tree = [1, 2, 3] [OK]

Hint: Inorder = left, root, right sequence [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Assuming Morris changes output order
• Mixing left and right subtree order

4. In this TypeScript snippet for Morris traversal, what is the bug?

while (current !== null) {
  if (current.left === null) {
    console.log(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;
      // Missing console.log here
      current = current.right;
    }
  }
}

medium

A. Incorrect initialization of predecessor variable.

B. Using '===' instead of '==' in while condition.

C. Not updating current to current.left in else block.

D. Missing printing current.val before moving right after restoring link.

Solution

1. Step 1: Identify missing output in else block

   When restoring the tree link, the node's value must be printed before moving right, else node is skipped.

2. Step 2: Effect of missing print

   Without printing current.val in the unthreading step, nodes with left subtrees are skipped in the output, causing incomplete traversal results.

3. Final Answer:

   Missing printing current.val before moving right after restoring link. -> Option D

4. Quick Check:

   Missing console.log(current.val) in unthreading step causes skipped nodes [OK]

Hint: Print node value when restoring threaded link [OK]

Common Mistakes:

• Ignoring print statement placement
• Confusing predecessor initialization
• Thinking '===' causes infinite loop

5. Given a binary tree with nodes:

      4
     / \
    2   5
   / \
  1   3

Using Morris inorder traversal, what is the exact sequence of node values printed, and why does this method not use extra memory?

hard

A. [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion.

B. [4, 2, 1, 3, 5]; uses recursion internally.

C. [1, 3, 2, 4, 5]; uses a stack to track nodes.

D. [5, 4, 3, 2, 1]; modifies tree permanently.

Solution

1. Step 1: Determine inorder traversal sequence

   Inorder visits left subtree, node, right subtree. For this tree, sequence is 1, 2, 3, 4, 5.

2. Step 2: Explain Morris traversal memory usage

   Morris traversal creates temporary threaded links to predecessor nodes, avoiding stack or recursion, thus using O(1) extra space.

3. Final Answer:

   [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion. -> Option A

4. Quick Check:

   Inorder = [1,2,3,4,5], O(1) space by threading [OK]

Hint: Inorder sequence + threaded links = no extra memory [OK]

Common Mistakes:

• Mixing traversal order
• Assuming recursion or stack used
• Believing tree is permanently changed