Morris Traversal

Please select Pre-order, In-order, or Post-order below to start.

Current Node (curr)

Predecessor (prev)

Visited

Thread

0 / 0

Speed: 1.0x

Visited Nodes:

Please select a mode to start...

Execution Log:

Code Trace (Select Mode)

let curr = root;
while (curr !== null) {
    if (curr.left === null) {
        visit(curr);
        curr = curr.right;
    } else {
        let prev = curr.left;
        while (prev.right && prev.right !== curr) {
            prev = prev.right;
        }
        if (prev.right === null) {
            prev.right = curr;
            curr = curr.left;
        } else {
            prev.right = null;
            visit(curr);
            curr = curr.right;
        }
    }
}

let curr = root;
while (curr !== null) {
    if (curr.left === null) {
        visit(curr);
        curr = curr.right;
    } else {
        let prev = curr.left;
        while (prev.right && prev.right !== curr) {
            prev = prev.right;
        }
        if (prev.right === null) {
            visit(curr); // Visit before threading
            prev.right = curr;
            curr = curr.left;
        } else {
            prev.right = null;
            curr = curr.right;
        }
    }
}

let dummy = new TreeNode(0);
dummy.left = root;
let curr = dummy;
while (curr !== null) {
    if (curr.left === null) {
        curr = curr.right;
    } else {
        let prev = curr.left;
        while (prev.right && prev.right !== curr) {
            prev = prev.right;
        }
        if (prev.right === null) {
            prev.right = curr;
            curr = curr.left;
        } else {
            prev.right = null;
            reverseVisit(curr.left, prev);
            curr = curr.right;
        }
    }
}