Binary Trees (Part 4) - Discussing (in) Depth-First Traversals
Tags: todayisearched, javascript, tutorial
Published: 2019-12-09 17:10:32

***Prerequisites:*** 
*It'd obviously be beneficial to have some knowledge of [binary trees](https://dev.to/jenshaw/the-basics-of-binary-trees-2kf8) and [binary-search trees](https://dev.to/jenshaw/binary-search-trees-are-the-best-gkk) since this article is about binary tree traversals. Also, a concept that is frequently mentioned here and used in the context of binary trees is [recursion](https://medium.com/@chopra.chet/tech-blog-5156e152a608). If you're not familiar with any of these, I'd highly recommend you catch up on them first before reading further.*

***

## Traversing Through Binary Trees
This week, we'll be exploring **Binary Tree Traversals**!

![Smithers struggling to traverse through a forest brush](https://media.giphy.com/media/l2JeavIMKpXLaJYXK/giphy.gif)

<center><h6>Not this kind of tree traversal, although sometimes the struggle feels the same.</h6></center>

First, I'll briefly explain the two types of traversals and searches, [**Depth-First Search (DFS)** and **Breadth-First Search (BFS)**](#searches). Then, I'll focus on the three [DFS methods](#dfs), [**Pre-**](#pre-order), [**Post-**](#post-order), and [**In-Order**](#in-order). For each one, I'll share a tip to help you remember how each traversal works, explain how the traversal is used, and demonstrate what it would look like visually and in code.

Sounds like an adventure! Let's go!

![Totoro and gang hiking through the forest](https://media.giphy.com/media/gqh8uVtwvemTm/giphy.gif)

***

## First, a Quick Story about Tree Traversals and Video Games
![Betrayal at Krondor Opening Title](https://i.ytimg.com/vi/9BA167Scd4E/maxresdefault.jpg)
<center><h6>Betrayal at Krondor - the greatest RPG of all time</h6></center>

I remember obsessively playing my all-time favorite RPG, [*Betrayal at Krondor*](https://en.wikipedia.org/wiki/Betrayal_at_Krondor), and spending many endless hours getting helplessly lost trying to explore various towns, caves, tunnels, and other maze-like areas. There were times when I got so frustrated, I would reset the level so that I could strategize and test new ways to get through them without wasting so much effort. 

![A map of Krondor](https://www.abandonwaredos.com/public/aban_files_giochi/krondor_map.gif)

Here was the strategy I ultimately came up with:
- Whenever I encountered a split in the path, I would always take the left turn. 
- And when I ever encountered a dead-end, I would backtrack to the split-off where I would take the next unexplored path to the left. 

This strategy worked extremely well for me in the end because decision-making at the crossroads was a super straightforward process that required very little thought, and I never experienced again the same level of head-spinning confusion and anguish that I had when I was choosing paths arbitrarily. Most of all, I was able to explore every single path and find every treasure chest, character, and baddie that existed within the maze. And I was *always* able to (eventually) find the exit. 

The best part of recalling this experience is realizing that, as a child, I was unknowingly applying a common binary tree traversal strategy, in-order traversal! 

![Smart!](https://media.giphy.com/media/hFROvOhBPQVRm/giphy.gif)

Now you know that the traversals we'll learn about here aren't just for trees: they can be applied to real-life situations, and you've probably already been using them!

***

## Let's Get into Binary Tree Traversals!
So, what does it mean to *traverse a tree*?

To ***traverse*** means to *move or pass through*, so when we're traversing and searching through a tree, we're moving through it by ***visiting each node along every branch until we encounter what we're looking for***. 

When any node in a binary tree could potentially branch out in two directions, it can quickly become overwhelming and confusing for us when we have to consider efficient yet thorough ways to traverse the tree and find the target value. It's a lot like finding the exit in a maze without a map. 

Fortunately, there are several commonly used methods that can help us systematically traverse through trees!

<a name="searches"></a>
***

## Depth-First Search vs. Breadth-First Search
There are two broad categories of tree traversals and searches, **Depth-First Search (DFS)** and **Breadth-First Search (BFS)**. Both use unique approaches that allow us to visit every node in a tree.

![Depth-First Search through a binary tree](https://media.giphy.com/media/ii2FtzyirI4MXpoxX4/giphy.gif)
**Depth-First Search** focuses on recursively processing nodes along a path between the root node and the leaf nodes. So imagine we're traversing straight down a path -- when a leaf node is finally reached, we *backtrack* from there and return back up our previously traversed path until we reach the first un-explored branch, and then we traverse that branch. This cycle of exhaustively exploring then backtracking repeats until all of the nodes of the tree have been visited.

![Breadth-First Search through a binary tree](https://media.giphy.com/media/iD6qdVmNOZH9frN6J4/giphy.gif)
**Breadth-First Search** is also known as a **Level-First Search** (Personally, I prefer the term Level-First because it emphasizes the concept of traversing by **levels**. That - and I like simple words.) With BFS, we search all the nodes ***level by level***, from the top of the tree to the bottom. This means that at the first level, we'd visit the root node, then on the second level, we'd visit its two children, and at each deeper level, we'd visit *all* the descendants of that same generation, including children, their siblings, and their cousins. 

<a name='dfs'></a>
***

## Depth-First Traversals
Here, we'll focus on these three Depth-First Searches.

1. **Pre-Order**
2. **In-Order**
3. **Post-Order**

Each of these traversal methods is an algorithm or set of directions that dictates the order that we visit nodes and their subtrees. 

Search | Order | | |
---: | :---: | :---: | :---
**pre-** | **ROOT** | left | right
**in-** | left | **ROOT** | right 
**post-** | left | right | **ROOT**

Although the traversal order changes with each method, there's one pattern that remains consistent: *The left node is* ***always*** *visited before the right node*.

Also pay attention to the *prefixes* of each search name because they'll help us better anticipate and understand what's going on. 

- ***Pre-*** means '*before*', so in this order, the root will be visited **first** before either the left or right nodes.

- Next, think of ***-in*** as in *inside*, and see how the root is located **in** the middle of the node order.

- Finally, ***-post*** means '*after*', so in this order, the root will be visited **last**, *after* the left and right nodes.

Now you can easily remember the respective orders of pre-order, in-order, and post-order!

![You guys are so smart!](https://media.giphy.com/media/3o7bukEYVSINz9FwKQ/giphy.gif)

<a name='in-order'></a>
***
## In-Order - Left, Root, Right
With an in-order search, we traverse the tree from left to right, bottom to top, and its often used to *print out a list of visited nodes*. 

When used on a Binary-Search Tree where values are sorted with smaller values to the left and larger values to the right, you'd get *a list of increasing values*.

### Steps to In-Order Traversal:
1. Traverse the **left subtree** by recursively calling `inOrder` function
2. Process the **root value** by pushing it into `nodes`
3. Traverse the **right subtree** by recursively calling `inOrder` function

![In-Order Traversal through a binary tree](https://media.giphy.com/media/cOosHV2GzVkdLwD2IG/giphy.gif)

### Code: Writing the inOrder Function
```javascript
let nodes = [];

const inOrder = root => {
  if (root.left) inOrder(root.left)
  nodes.push(root.value);
  if (root.right) inOrder(root.right);
}

inOrder(root);
return nodes;
```
Before writing the `inOrder` function, we assign an empty array to a variable called `nodes`, which will later compile a list of node values processed in-order. As we traverse the tree, new node values will be added to it.

`inOrder` is the function that will determine the steps and order that nodes will be visited. By using it we'll recursively traverse the left subtree, process the node, then recursively traverse the right subtree.

### Code Explanation
Let's say we call the `inOrder` function on the root node at the top of the tree. From the root node, we check for a left node, and if one exists, the function calls itself again using that node. Then from *that* node, the process is repeated. As we move down the tree leftwards, we're creating a stack of `inOrder` calls until we can't move leftwards anymore. 

When we finally reach the leftmost node at the end of the branch, the most recent `inOrder` call runs the following line that pushes the root value to `nodes`, and then the last line that checks if there's a right node to traverse. (In this case, there isn't, but if there were, `inOrder` would be called again to process the right node and its descendants.)

When that most recent call is complete, it's removed from the call stack, and as a result, we backtrack to the previous node that `inOrder` was called with, process that node there, then follow down its right subtree.

<a name='pre-order'></a>
***

## Pre-Order - Root, Left, Right
Pre-order search, similarly to in-order search, lets us print a list of the visited nodes, but this time from top to bottom, left to right. Pre-order traversal is often used to *copy a tree*. 

### Steps to Pre-Order Traversal:
1. Process the **root value** by pushing it into `nodes`
2. Traverse the **left subtree** by recursively calling `preOrder` function
3. Traverse the **right subtree** by recursively calling `preOrder` function

![Pre-Order Traversal through a binary tree](https://media.giphy.com/media/dxCT5ok6OM7MS5zAqA/giphy.gif)

### Code: Writing a preOrder Function
```javascript
let nodes = [];

const preOrder = root => {
  nodes.push(root.value);
  if (root.left) preOrder(root.left)
  if (root.right) preOrder(root.right);
}

preOrder(root);
return nodes;
```

### Code Explanation
The process for pre-order search is very similar to in-order search, only that the order of nodes processed is rearranged to root, left, then right.

When we want to [construct a binary-search tree](https://www.techiedelight.com/build-binary-search-tree-from-preorder-sequence/) or [a new tree](https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/), we can use the pre-order as well as in-order lists to help us build it from the top down. The root node, the first of the printed list, would be established first before introducing the children nodes that connect to it.

<a name='post-order'></a>

***
## Post-Order - Left, Right, Root
Post-order traversal can be used to *delete a tree* one node at a time, starting with the children, then their parent, all the way up to the root node. 

### Steps to Post-Order Traversal:
1. Traverse the **left subtree** by recursively calling `postOrder` function
2. Traverse the **right subtree** by recursively calling `postOrder` function
3. Process the **root value** by pushing it into `nodes`

![Post-Order Traversal through a binary tree](https://media.giphy.com/media/Ri8whiqAwDo8A11rPY/giphy.gif)

### Code: Writing the postOrder Function
```javascript
let nodes = [];

const postOrder = root => {
  if (root.left) postOrder(root.left)
  if (root.right) postOrder(root.right);
  nodes.push(root.value);
}

postOrder(root);
return nodes;
```

### Code Explanation
Post-order traversal is almost the reverse of pre-order. While pre-order processes root, left, right, essentially from top to bottom, post-order processes left, right, and root, from bottom to top. 

If we were to apply it by deleting nodes from a tree, we'd process each external or leaf node, assign null to it, and effectively remove each one from the tree, then exposing internal nodes and making them the new leaf nodes ready to be removed later.

***

## Wrap-Up & Conclusion
That's it for Depth-First Traversals! There are many other kinds of depth-first traversals

That was a lot of information to take in, but now that you know more about traversals, they probably seem a lot less scary and overwhelming than before! 

Next week and coming up last in my five-part Binary Tree series is the Breadth-First Traversal! Whew! We got this!

![Dust off](https://media.giphy.com/media/43JOOvm7SbDbHTKQUm/giphy.gif)

***
## Resources:
If you want to see a video demonstration of all three depth-first traversals, this is an excellent view:
- [Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal.](https://www.youtube.com/watch?v=BHB0B1jFKQc&t=290s) - Back to Back SWE

If you're interested in knowing more about constructing binary-search trees with in-order and pre-order sequences, check out these links:

- [Construct Tree from given Inorder and Preorder traversals](https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/) - GeeksForGeeks
- [Build a Binary Search Tree from a PreOrder Sequence](https://www.techiedelight.com/build-binary-search-tree-from-preorder-sequence/) - Techie Delight

And for more about deleting trees using a post-order sequence, take a look at this:
- [Write a Program to Delete a Tree](https://www.geeksforgeeks.org/write-a-c-program-to-delete-a-tree/) - GeeksForGeeks

***
For more information on binary trees, check out these other blogs from my 5-part binary tree series!

* [Part 1 - The Basics](https://dev.to/jenshaw/the-basics-of-binary-trees-2kf8)
* [Part 2 - Binary Search Trees (Insertion and Search)](https://dev.to/jenshaw/binary-search-trees-are-the-best-gkk)
* [Part 3 - Node Deletion](https://dev.to/jenshaw/deleting-nodes-in-binary-search-trees-4nhm)
* [Part 5 - Breadth-First Traversals](https://dev.to/jenshaw/binary-trees-stay-abreast-of-breadth-first-search-3pi7)