Skip to content

Instantly share code, notes, and snippets.

@anish000kumar
Last active August 28, 2021 05:29
Show Gist options
  • Save anish000kumar/7927c87003026b313eee3843181bb780 to your computer and use it in GitHub Desktop.
Save anish000kumar/7927c87003026b313eee3843181bb780 to your computer and use it in GitHub Desktop.
PostOrder traversal using parent pointer
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment