inOrder traversal with parent pointer

parentInOrder.js

function Node(value, parent = null){
  this.value = value
  this.left = null
  this.right = null
  this.parent = parent
  
}

// create tree

const root = new Node(2)
root.left = new Node(3, root)
root.right = new Node(9, root)
root.left.left = new Node(21, root.left)
root.left.right = new Node(32, root.left)
root.left.right.right = new Node(16, root.left.right)
root.left.right.right.left = new Node(4, root.left.right.right)
root.left.right.right.right = new Node(5, root.left.right.right)


// recursive preOrder approach

function inOrder(root){
  if(!root) return
  
  inOrder(root.left)
  console.log(root.value)
  inOrder(root.right)
}



// using parent pointer
function nextInOrder(root){
   if(!root) return
  
   if(root.right){
     let curr = root.right
     while(curr && curr.left) curr = curr.left
     return curr
   }
  
   let parent = root.parent
   
   while(parent && parent.right === root) {
     root = root.parent
     parent = parent.parent
   }
     
   return parent
}

function parentInOrder(root){
  // start at the left most node
  while(root && root.left){
    root = root.left
  }
  console.log(root.value);
  let curr = root
  while(true){
    const nxt = nextInOrder(curr)
    if(!nxt) break
    curr = nxt
    console.log(curr.value)
  }
}



// result
inOrder(root)
console.log("----------")
parentInOrder(root)