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.