# Tree: efficient traversal with parent pointer

In the [first part of this series](https://stackfull.dev/series/tree-javascript) 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:
```javascript
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):

```javascript
function Node(value){
  this.value = value
  this.left = null
  this.right = null
  this.parent = null // added parent field
}
```
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.

```javascript

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: 

![Screenshot 2021-08-28 at 7.36.28 AM.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1630116404318/FzFoTp0y5.png)


## 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. 

1.  First off, we're dealing with preOrder here, that means we're looking for following order:
```
root -> left -> right
```
2. That means if we're already at current node, we want to look for the left child node as successor. 
3. 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.
4. 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:

```javascript
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 // we backtracked till root, so no successor
   
   return parent.right
}
```

Here's  the visual cue for better understanding.

![Screenshot 2021-08-28 at 9.08.26 AM.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1630121945520/GQOxqsVuU.png)

Here's a [link to a gist](https://gist.github.com/anish000kumar/2bd0d9932bef066e7c72a18e8814b0c2) 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:

1. For InOrder successor we are looking to traverse in following way:
```
left -> root -> right
```
2. 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.

3. 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). 

4. 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:

```javascript
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:

![Screenshot 2021-08-28 at 10.14.58 AM.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1630125933639/Zw-NhbXIX.png)

[Link to gist](https://gist.github.com/anish000kumar/169899323d4b651651408b711beb21f6) on this idea.

### PostOrder successor
Let's follow similar thought process for finding the postOrder successor:

1. For postOrder, we are looking to traverse in following way:
```
left -> right -> root
```
2. 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.

3. If we're reaching the parent from it's right child, that means parent itself is successor, by the definition in #1

4. 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:

```javascript
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
}
```


![Screenshot 2021-08-28 at 11.13.50 AM.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1630129446688/K8EtBM7a-f.png)

[Link to gist](https://gist.github.com/anish000kumar/7927c87003026b313eee3843181bb780) 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:

```javascript
function preOrder(root){
  // first node
  console.log(root.value);

  let current = root
  while(true){
    const next = preOrderSuccessor(current)
    if(!next) break

    // do something
    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:

```javascript
function inOrder(root){
  // start at the left most node
  while(root && root.left){
    root = root.left
  }

  // first node
  console.log(root.value);

  let current = node
  while(true){
    const next = inOrderSuccessor(current)
    if(!next) break

    // do something
    console.log(current.value)

    current = next
  }
}
```

## PostOrder traversal

Very similar to InOrder approach above:

```javascript
function postOrder(root){
  // start at the left most node
  while(root && root.left){
    root = root.left
  }

  // first node
  console.log(root.value);

  let current = node
  while(true){
    const next = postOrderSuccessor(current)
    if(!next) break

    // do something
    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.

%%[message]