Skip to content

Instantly share code, notes, and snippets.

@anish000kumar
Created August 28, 2021 04:32
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save anish000kumar/169899323d4b651651408b711beb21f6 to your computer and use it in GitHub Desktop.
inOrder traversal with 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 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment