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 thenD 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