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