Depth First Search (DFS) tree traversal can be performed with any of the following strategies: "inorder", "postorder", and "preorder". What's the difference? The difference is actually quite simple  it is simply the order in which you visit the node compared to when you traverse the children of the node.
The Basics
To better understand what this means, let's talk about the basics of tree traversal. For simplicity, we'll assume we're only working with binary trees where each node can have at most two children, a left child and a right child.
For each node of the binary tree, there are three steps to complete:
 traverse the left subtree
 traverse the right subtree
 do something with the node itself  here we'll record it's value
So with these three steps established, we can place them in their correct order for each DFS strategy:
Preorder:
In preorder, we first process the node:
 Do something: record the node's value
 Traverse the left
 Traverse the right
Postorder:
In postorder, we process the node last:
 Traverse the left
 Traverse the right
 Do something: record the node's value
Inorder:
For inorder, we'll process the node in between traversing each side:
 Traverse the left
 Do something: record the node's value
 Traverse the right
As we can see from the steps above, we do the exact same thing in each strategy, just in a slightly different order. This means we can use the same lines of code for each method. We'll just need to make a slight alteration in the order.
The Code
Tree Structure
We'll assume we have a Binary Tree class that looks something like this Binary Search Tree:
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(val) {
const newNode = new Node(val);
if (!this.root) {
this.root = newNode;
return this;
}
let curr = this.root;
while (true) {
if (curr.val > val) {
if (!curr.left) {
curr.left = newNode;
return this;
}
curr = curr.left;
} else if (curr.val < val) {
if (!curr.right) {
curr.right = newNode;
return this;
}
curr = curr.right;
} else {
return this;
}
}
}
}
Depth First Search Pseudo Code
We will write a function that accepts a node (the root of a tree on the first pass) and returns an array of all the values in that tree, after visiting all of the nodes once. Here, we'll use a recursive strategy.
 Our function will create an array,
visited
, to record the values of visited nodes.  Our base case will check if the node is null. If so, we'll return the empty array.

Otherwise we need to perform our three steps:
 add the value of the node to the
visited
array  Recursively call our function again, passing in the left child as the node and concatenating the return value of this function call to the
visited
array  Recursively call our function again, passing in the right child as the node and concatenating the return value of this function call to the
visited
array
 add the value of the node to the
After visiting all nodes in the tree, the
visited
array will be filled with the values of each node.Finally, we will return
visited
.
Depth First Search Function
For Pre Order (visit the node first) this looks like:
function dfsPreOrder(node) {
let visited = [];
if (!node) return visited; //base case
visited.push(node.val); //1. visit node
visited = visited.concat(dfsPreOrder(node.left)) //2. traverse left
visited = visited.concat(dfsPreOrder(node.right)) //2. traverse right
return visited;
}
For Post Order (visit the node last) this looks like:
function dfsPostOrder(node) {
let visited = [];
if (!node) return visited; //base case
visited = visited.concat(dfsPostOrder(node.left)) //1. traverse left
visited = visited.concat(dfsPostOrder(node.right)) //2. traverse right
visited.push(node.val); //3. visit node
return visited;
}
For In Order (visit the node in the middle) this looks like:
function dfsInOrder(node) {
let visited = [];
if (!node) return visited; //base case
visited = visited.concat(dfsInOrder(node.left)) //1. traverse left
visited.push(node.val); //2. visit node
visited = visited.concat(dfsInOrder(node.right)) //3. traverse right
return visited;
}
Top comments (0)