PreOrder traversal using parent pointer

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



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

function parentPreOrder(root){
  console.log(root.value);
  let curr = root
  while(true){
    const nxt = nextPreOrder(curr)
    if(!nxt) break
    curr = nxt
    console.log(curr.value)
  }
}



// result
preOrder(root)
console.log("----------")
parentPreOrder(root)