In the first part of this series we looked at recursive and iterative approaches for traversing through a binary tree. If you haven't looked through it yet, I highly recommend you to check it out first. I'll wait here, I promise ;)
In real life applications, it's quite common for tree nodes to have a parent field: a field which points to the parent node, hence also called as the parent pointer. Let's take the example of DOM in browser. Say we select any node using the following:
const element = document.querySelector("#id")
Now, we would find element.parentNode to be pointing to the element's parent.
In this article, we'll look at how we can use these parent pointers to make the traversal more efficient. I'll explain what do I mean by 'more efficient' in a bit. In the next article, we'll also see how we can use the lessons learnt here to create myQuery library (a lightweight jQuery clone) from scratch.
Updating our Node definition:
First off, we need to update our Node function (side-note: in OOPs world you may call this a class instead, because this function is always to be invoked with the new operator):
function Node(value){
this.value = value
this.left = null
this.right = null
this.parent = null
}
Nothing fancy here! Now let's see how we can use this new Node definition to create a similar tree, as we did in last article.
const root = new Node(2)
const left = new Node(1)
root.left = left
left.parent = root
const right = new Node(3)
root.right = right
right.parent = root
Alright so that was simple too. We simply needed to ensure parent fields point to the parent node. Here's a visual reference for the final tree we get using the code above:
Finding the successor
PreOrder successor
Let's do something more fun. How about finding the next node in preOrder traversal of tree given the current node and the fact that each node has a parent pointer. Let me rephrase this question for clarity:
How can be find out the preOrder successor of any node in a binary tree? Assume that each node has a parent pointer.
Let's try to dissect this problem.
- First off, we're dealing with preOrder here, that means we're looking for following order:
root -> left -> right
- That means if we're already at current node, we want to look for the left child node as successor.
- What if there's no left child at all ? Well in that case, we look for the right child and if it's there, that's the successor.
- If there's no left or right child, then we need to backtrack (keep going upwards towards the parent). We keep backtracking till parent is being reached via it's right child (because that means preOrder is complete for whole subtree under the parent, by definition on #1).
So here's what the final algorithm would look like:
function preOrderSuccessor(node){
if(!node) return
if(node.left) return node.left
if(node.right) return node.right
let parent = node.parent
while(parent && parent.right === node) {
node = node.parent
parent = parent.parent
}
if(!parent) return null
return parent.right
}
Here's the visual cue for better understanding.
Here's a link to a gist on this idea, in case you want to explore it for yourself.
InOrder successor
Finding InOrder successor is pretty similar. Let's go step by step:
- For InOrder successor we are looking to traverse in following way:
left -> root -> right
If we're at current node, and there's anything on it's right then we can get the successor by finding the leftmost node on the right subtree.
If there's no right child, then we need to backtrack (move upwards). We keep moving upwards till parent is reached via it's right child, because that means whole subtree has been traversed already (by definition in #1).
Once we find the nearest parent, which has been found via it's left child, this it is returned as the successor. Why? Because it means it's a node whose left tree has been explored, so by definition in #1, the node itself is now the successor.
Here's the final algorithm:
function inOrderSuccessor(node){
if(!node) return
if(node.right){
let current = node.right
while(current && current.left) current = current.left
return current
}
let parent = node.parent
while(parent && parent.right === node) {
root = node.parent
parent = parent.parent
}
if(!parent) return null
return parent
}
Visual cue:
Link to gist on this idea.
PostOrder successor
Let's follow similar thought process for finding the postOrder successor:
- For postOrder, we are looking to traverse in following way:
left -> right -> root
So, if we're at any node it means it's left and right subtree has already been explored. That means we need to look at the parent for successor.
If we're reaching the parent from it's right child, that means parent itself is successor, by the definition in #1
If we're reaching the parent from it's left child, that means parent's right child is to be explored next (as per definition in #1). So now we need to simply return the leftmost node in parent's right child as successor.
Here's the final algorithm:
function postOrderSuccessor(node){
if(!node) return
let parent = node.parent
if(!parent) return null
if(parent.right === node). return parent
let current = parent.right
while(current && (current.left || current.right)){
current = (current.left || current.right)
}
return current
}
Link to gist to play around with this idea.
Using successor algorithms for better traversal
Why ?
Why do we need to use parent field to come up with a traversal algorithm at all? It's a valid question, since we've already come up with recursive and iterative approaches to traverse the tree, that too without the need for parent field.
The reason why we're doing this is because of added space complexity in our previous approaches. If you remember we needed to use one or two stacks (depending on traversal method) in the previous article, to get any of the traversal algorithms working. Even in recursive approach, though we're not directly using a stack but recursion itself is based on call-stacks, so there's hidden in-memory stack being used there as well. The problem is that size of this stack is going to increase with depth of our tree, hence it's not the best solution since we've a way to do the same task while spending lesser space . By using the parent pointer we can get rid of those stacks completely, saving us significant space i.e. going from space complexity of O(logN) where N denotes size of a balanced tree to O(1). Let's see how.
PreOrder traversal
For preOrder traversal, we start at the root of the tree. Afterwards, we can keep fetching the preOrder successor using the algorithm above to traverse the whole tree:
function preOrder(root){
console.log(root.value);
let current = root
while(true){
const next = preOrderSuccessor(current)
if(!next) break
console.log(next.value)
current = next
}
}
InOrder traversal
For InOrder traversal, starting node would be the left-most node of the tree. Thereafter we can keep fetching the successor using the algorithm above to traverse the whole tree:
function inOrder(root){
while(root && root.left){
root = root.left
}
console.log(root.value);
let current = node
while(true){
const next = inOrderSuccessor(current)
if(!next) break
console.log(current.value)
current = next
}
}
PostOrder traversal
Very similar to InOrder approach above:
function postOrder(root){
while(root && root.left){
root = root.left
}
console.log(root.value);
let current = node
while(true){
const next = postOrderSuccessor(current)
if(!next) break
console.log(current.value)
current = next
}
}
Quick exercise
Can you come up with algorithms for finding predecessor (inOrder, preOrder and postOrder) if each node has a parent pointer ? It would be a fun exercise. Try it out and let me know in the comments.
