Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
PreOrder 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 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment