Hi folks, welcome back.

In this article, we will

Implement a Depth-First Traversal

Differentiate different Tree Traversal Methods, namely, pre-order, post-order, in-order

**Depth-First Search**

π Is the way to traverse a Binary (Search) Tree that prioritizes **DEPTH** rather than Breadth.

π The idea is **KEEP TRAVERSING DOWN** either the LEFT or RIGHT subtree until there are **NO MORE NODES LEFT.**

*Images Source: Coderbyte*

By applying the DFS algorithm, as a result, we'll get the values like this `A, B, D, E, C, F`

## HOW to implement the DFS Algorithm?

While the BFS requires a Queue underneath the hood.

The DFS requires a Stack. (LIFO)

We **add** things to the **top** of the stack.

We **also remove** things from the **top** of the stack.

Here is the **potential steps** we can take to implement DFS

π Init the Stack with a root node.

π Next, we go ahead and POP the current node `A`

out of the Stack. That's also mean we're visiting this `A`

node right now.

π Let's print the value of `A`

node, then consider its children (**B and C)**

Here we pushed the `C`

and then `B`

on top of the stack. The order is matter here.

We prioritize going DEPTH FIRST. It means we want to print out `B`

after `A`

Stack is the Data Structure with LIFO (Last In First Out) mental model.

That's why we want the `B`

on top of the stack just for now.

Next, we pop `B`

out of the stack, and print its value.

Then move on, applying the same pattern on all the children of `B`

, we push `E`

and **then**`D`

on top of the stack.

On top of the stack, we have the value of `D`

now.

Next, we pop off `D`

and then `E`

out of the Stack. They have NO children.

We finished the DFS on the left subtree.

Now we back to the `C`

We pop `C`

out of the Stack, and print its value.

`C`

only having 1 children is `F`

Let's push `F`

on top of the stack.

Pop `F`

off the stack and print its value.

Check for `F`

children, **there is no more NODE left.**

Our stack is now **EMPTY**. We **DONE** with our algorithm and printed out ALL the node values.

# Let's code the DFS Algorithms

```
// BINARY TREE
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
};
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
const g = new Node('g');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
```

```
const depthFirstPrint = (root) => {
const stack = [ root ];
while (stack.length) {
const current = stack.pop();
console.log(current.value);
if (current.right) stack.push(current.right);
if (current.left) stack.push(current.left);
};
};
depthFirstSearch(a);
// Printed Value: A, B, D, E, C, F
```

### Complexity Analysis

Time: O(n) - Traversing through every node in the Tree.

Space: O(n) - The amount of space the Stack occupies at worst case - need to store every node of the tree inside.

π We will probably always use the Stack to implement the DFS Algorithm

We just have a great Iterative DFS solution.

We can also use the stack but in the implicit approach with recursive.

The code for the DFS Recursive

```
const depthFirstRecursivePrint = (root) => {
if (root === null) return;
console.log(root.value);
depthFirstRecursivePrint(root.left);
depthFirstRecursivePrint(root.right);
};
depthFirstRecursivePrint(a);
// Printed Value: A, B, D, E, C, F
```

# 3 Different Variations of Depth First Traversal

# Pre-order (Self - Left - Right)

Exactly what we just did above.

We call **PRE** order because we **printed** out the **Parent** Node's **valueBEFORE BOTH of the Children.**

```
const preOrder = (root) => {
if (root === null) return;
console.log(root.value);
preOrder(root.left);
preOrder(root.right);
};
preOrder(a);
// Printed Value: A, B, D, E, C, F
```

# Post-order (Left - Right - Self)

The key pattern here is: we only printed out the node's value **AFTER both of its children.**

```
const postOrder = (root) => {
if (root === null) return;
postOrder(root.left);
postOrder(root.right);
console.log(root.value);
};
postOrder(a);
// Printed Value: D, E, B, F, C, A
```

# In-order (Left - Seft - Right)

Key pattern here, print the node's value in between the value of left and right nodes.

After left, but before right.

```
const inOrder = (root) => {
if (root === null) return;
inOrder(root.left);
console.log(root.value);
inOrder(root.right);
};
inOrder(a);
// Printed Value: D, B, E, A, C, F
```

# Practice Exercise:

Write a function `sumTreeDFS`

that take in the root of a binary tree as an argument.

The function should return the sum of all values in the tree.

Assume that the tree only contains number value.

```
const a = new Node(3);
const b = new Node(2);
const c = new Node(7);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(5);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
```

## Solution

### Iterative

```
const sumTreeDFS = root => {
const stack = [ root ];
let sum = 0;
while (stack.length) {
const current = stack.pop();
sum += current.value;
if (current.right) stack.push(current.right);
if (current.left) stack.push(current.left);
};
return sum;
}
sumTreeDFS(a) // 19
```

### Recursive

```
const sumTreeDFS = root => {
if (root === null) return 0;
return sumTreeDFS(root.left) + root.value + sumTreeDFS(root.right)
}
sumTreeDFS(a) // 19
```

### Complexity Analysis

Time: O(n) - Iterating through every node in the Tree.

Space: O(n) - Keep track of the Callstack