Morris Traversal

MorrisTraversal.js

//https://gist.github.com/carefree-ladka/f141d0efcefb0260f380daea7cdab425

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

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;
};


//Postorder
function postorderTraversal(root) {
  const result = [];
  let current = root;

  while (current) {
    if (!current.right) {
      result.push(current.val);
      current = current.left;
    } else {
      let successor = current.right;
      while (successor.left && successor.left !== current) {
        successor = successor.left;
      }
      if (!successor.left) {
        result.push(current.val);
        successor.left = current;
        current = current.right;
      } else {
        successor.left = null;
        current = current.left;
      }
    }
  }
  return result.reverse();
}

// Example usage:
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);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);


/* 
                     1
                    / \
                   2   3
                  / \ / \
                 4  5 6 7

*/

console.log(preorderTraversal(root)); //[1, 2, 4, 5, 3, 6, 7]
console.log(inorderTraversal(root)); //[4, 2, 5, 1, 6, 3, 7]
console.log(postorderTraversal(root)); //[4, 5, 2, 6, 7, 3, 1]