Morris Traversal

MorrisTraversal.js

const inorderTraversal=function(root){
    let node = root;
    const result=[]
  while (node) {
    if (!node.left) {
      result.push(node.val);
      node = node.right;
    } else {
      const predecessor = findPredecessor(node);
      if (predecessor.right === node) {
        //We have a cycle
        predecessor.right = null; //Break the cycle
        // console.log(node.val);
          result.push(node.val);
        node = node.right;
      } else {
        predecessor.right = node; //if visiting for the first time, create a cycle
        node = node.left;
      }
    }
  }
    return result
}


function findPredecessor(root){
    let node=root.left
    while(node.right && node.right!==root){
        node=node.right
    }
    return node
}


//Preorder

const preorderTraversal = function(root) {
    let node = root;
    const result = [];
    while (node) {
        if (!node.left) {
            result.push(node.val);  // Visit the node
            node = node.right;
        } else {
            const predecessor = findPredecessor(node);
            if (predecessor.right === node) {
                // We have a cycle
                predecessor.right = null;  // Break the cycle
                node = node.right;
            } else {
                result.push(node.val);  // Visit the node
                predecessor.right = node;  // Create a cycle
                node = node.left;
            }
        }
    }
    return result;
};

function findPredecessor(root) {
    let node = root.left;
    while (node.right && node.right !== root) {
        node = node.right;
    }
    return node;
}