PostOrder traversal using parent pointer

parentPostOrder.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 postOrder(root){
  if(!root) return
  
  postOrder(root.left)
  postOrder(root.right)
  console.log(root.value)
}



// using parent pointer
function nextPostOrder(root){
   if(!root) return
  
   let parent = root.parent
   
   if(!parent) return null
   
   if(parent.right === root){
     return parent
   }
  
   let current = parent.right
   
   while(current && (current.left || current.right)){
     current = (current.left || current.right)
   }
  
   return current
}

function parentPostOrder(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 = nextPostOrder(curr)
    if(!nxt) break
    curr = nxt
    console.log(curr.value)
  }
}



// result
postOrder(root)
console.log("----------")
parentPostOrder(root)