# Tree Traversal: In-Order, Pre-Order, Post-Order

## Course launching August 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

INCLUDE THE ITERATIVE SOLUTIONS IN SOME WAY? MAKE IT A BONUS HERE? IN REPL? JUST TELL THEM TO DO IT?

There are two methods to traverse trees: depth-first search (DFS) and breadth-first search (BFS).

DFS is the most common way, and it is performed by traversing to the leaf nodes. It goes as deep as it can and then moves on to the next branch. DFS is implemented using a stack or recursion.

BFS on the other hand traverse the tree by level and can also be called level-order traversal. So it will go all the way through level 1, then level 2, and follow this path until it reaches the last level. DFS is used to find the shortest path to a node.

DFS is much more common with trees, so we will discuss how it's done here, and then go into DFS vs BFS in more depth in the graph data structure section.

There are three ways to traverse a tree using DFS: in-order traversal, pre-order traversal, and post-order traversal.

## Traversal Implementations

For all the cases, we will only consider a binary search tree that has a `left`

and `right`

pointer.
The iterative solution is long and does not provide much additional insight, so we will only use the recursive solution.

You will notice that all the solutions look very similar - almost identical. The only difference is when we "visit" a node which is when we would use its data to add to the solution.

Since we are using recursion, we are building up a stack of function calls and it will unwind when we reach the leaf nodes.
What determines the order is if we "visit" the node before the recursive call, after visiting the `left`

node recursively or after visiting both the `left`

and `right`

nodes recursively.

The input function will be the following node implementation:

```
class BinaryTreeNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
```

In our case we will consider visiting the node just printing its data:

```
function visitNode(node) {
console.log(node.data);
}
```

### In-Order Traversal

In-order traversal is the most common and visits the nodes in ascending order. This will start with the smallest value at the left-most node and end at the largest value at the right-most node.

Use in-order traversal if you need to treat as (or check if) the nodes are in a sorted linear order.

```
function inOrderTraversal(node) {
if (node !== null) {
inOrderTraversal(node.left);
visitNode(node);
inOrderTraversal(node.right);
}
}
```

### Pre-Order Traversal

Pre-order traversal will always visit the current node before visiting its children. The root is the first node visited. The it follows the left path and visits each node as it encounters them. Afterwards, it follows the right paths and still visits the nodes as it encounters them before continuing on with the path.

Use this if you want to explore a given level before reaching the leaf node of a path.

```
function preOrderTraversal(node) {
if (node !== null) {
visitNode(node);
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
```

### Post-Order Traversal

For post-order traversal, you visit a node's children before visiting that node. This means that you will use it when you want to reach the leaves first. You visit the entire left subtree, then the entire right subtree, and then the root node of the subtree.

```
function postOrderTraversal(node) {
if (node !== null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
visitNode(node);
}
}
```

Table of Contents