Depth first traversal of Binary Trees in Javascript
Tags: algorithms, beginners, javascript, webdev
Published: 2020-07-15 03:20:42

---
title: Depth first traversal of Binary Trees in Javascript
published: true
description: Three types of depth first traversal in binary trees.
tags: algorithms, beginners, javascript, webdev
cover_image: https://i.imgur.com/2aCCEzo.jpg
---


<h1>Depth First Traversal in Binary Trees</h1>
<h5>Hello!</h5>
<p>In an effort to teach myself fundamentals that I might have missed in my rudimentary yet effective bootcamp experience, I'm going to cover some basics in a series about data structures and algorithms. As you might have surmised, in this post we're going to be discussing depth first traversal</p>
 
<p>
  A depth first traversal is a way of accessing every node in graph or binary
  tree.
</p>
<p>
  A depth first traversal is characterized by the direction of the traversal.
</p>
<p>
  In other words, we traverse through one branch of a tree until we get to a
  leaf, and then we work our way back to the trunk of the tree.
</p>

<p>
  In this post, I'll show and implement three types of depth first traversal.
</p>

<h2>
  Inorder traversal
</h2>
<p>
  As 'depth first' implies, we will reach the 'leaf' (a node with no children)
  by traveling downward in a recursive manner.
</p>
<p>
  Inorder traversal adheres to the following patterns when traveling
  recursively:
</p>
<ol>
  <li>Go to left-subtree</li>
  <li>Visit Node</li>
  <li>Go to right-subtree</li>
</ol>
<p>We can illustrate this concept with the follow gif</p>
![Inorder traversal](https://dev-to-uploads.s3.amazonaws.com/i/amr1issqea2n9yydiizi.gif)

<h2>Let's code!</h2>
<p>For the following examples we'll be using the Tree class I've defined below. </p>

```js
class Tree {
  constructor(value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
```
<p>Let's go ahead and create the tree we see in the example gif</p> 
```js
tree = new Tree(
  1,
  new Tree(2, new Tree(4, new Tree(8)), new Tree(5)),
  new Tree(3, new Tree(6, new Tree(9), new Tree(10)), new Tree(7))
);
```
<p>Finally, let's implement inorder traversal:</p>
```js
const inOrderTraversal = (node, cb) => {
  if (node !== undefined) {
    inOrderTraversal(node.left, cb);
    cb(node.value);
    inOrderTraversal(node.right, cb);
  }
};

inOrderTraversal(tree, console.log);
// 8, 4, 2, 5, 1, 9, 6, 10, 3, 7
```
<p>As you can see, the code mimics the steps outlined above.</p>
<p>The trickiest bit of this visualization is imagining the recursion until you hit the left-most leaf. I personally groan at the sight of recursion, but it's just something that has to be confronted with depth first traversal.</p> 
<h3>Fun fact:</h3>
<p><strong>Inorder Traversal of Binary Search Tree will always give you Nodes in sorted manner</strong></p>

<h2>
  Preorder traversal
</h2>
<p>
  Preorder traversal adheres to the following patterns when traveling
  recursively:
</p>
<ol>
  <li>Visit Node</li>
  <li>Go to left-subtree</li>
  <li>Go to right-subtree</li>
</ol>
<p>In other words, preorder is extremely similar to inorder except for the fact it will visit the root of the node first.</p>
![Preorder](https://dev-to-uploads.s3.amazonaws.com/i/g3w9bnl8evdtebofub0s.gif)

<p>Let's implement preorder traversal:</p>
```js
const preOrderTraversal = (node, cb) => {
  if (node !== undefined) {
    cb(node.value);
    preOrderTraversal(node.left, cb);
    preOrderTraversal(node.right, cb);
  }
};
preOrderTraversal(tree, console.log);
// 1, 2, 4, 8, 5, 3, 6, 9, 10, 7
```

<h2>
  Postorder traversal
</h2>
<p>
  Post traversal adheres to the following patterns when traveling
  recursively:
</p>
<ol>
  <li>Go to left-subtree</li>
  <li>Go to right-subtree</li>
  <li>Visit Node</li>
</ol>
<p>Once again, postorder is extremely similar to the others except for the fact it will visit the left subtree, then the right subtree and finally the node itself.</p>
![Postorder](https://dev-to-uploads.s3.amazonaws.com/i/yxahifv1817m9zh27axx.gif)

<p>Let's implement postorder traversal:</p>
```js
const postOrderTraversal = (node, cb) => {
  if (node !== undefined) {
    postOrderTraversal(node.left, cb);
    postOrderTraversal(node.right, cb);
    cb(node.value);
  }
};
postOrderTraversal(tree, console.log);
// 8, 4, 5, 2, 9, 10, 6, 7, 3, 1
```

<p>That wraps it up for depth first traversal...as far as I know.
Please let me know if you've learned anything or I've made any egregious mistakes!</p>

<p>Till next time,
cheers!</p>