# Binary Trees (Part 4) - Discussing (in) Depth-First Traversals

###
Jenny Shaw
*Updated on *
γ»9 min read

*Prerequisites:*

*It'd obviously be beneficial to have some knowledge of binary trees and binary-search trees 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. 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**!

###### Not this kind of tree traversal, although sometimes the struggle feels the same.

First, I'll briefly explain the two types of traversals and searches, **Depth-First Search (DFS)** and **Breadth-First Search (BFS)**. Then, I'll focus on the three DFS methods, **Pre-**, **Post-**, and **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!

## First, a Quick Story about Tree Traversals and Video Games

###### Betrayal at Krondor - the greatest RPG of all time

I remember obsessively playing my all-time favorite RPG, *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.

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!

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!

## 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** 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** 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.

## Depth-First Traversals

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

**Pre-Order****In-Order****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.

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

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

means '*-post**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!

## 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:

- Traverse the
**left subtree**by recursively calling`inOrder`

function - Process the
**root value**by pushing it into`nodes`

- Traverse the
**right subtree**by recursively calling`inOrder`

function

### Code: Writing the inOrder Function

```
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.

## 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:

- Process the
**root value**by pushing it into`nodes`

- Traverse the
**left subtree**by recursively calling`preOrder`

function - Traverse the
**right subtree**by recursively calling`preOrder`

function

### Code: Writing a preOrder Function

```
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 or a new tree, 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.

## 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:

- Traverse the
**left subtree**by recursively calling`postOrder`

function - Traverse the
**right subtree**by recursively calling`postOrder`

function - Process the
**root value**by pushing it into`nodes`

### Code: Writing the postOrder Function

```
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!

## 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. - 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 - GeeksForGeeks
- Build a Binary Search Tree from a 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 - GeeksForGeeks

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

Oh my god Jenny, that game was like half of my childhood. I don't think I've met anyone who was as into it as my brother and me. This, and of course a thorough and informative breakdown of DFS, has brightened my day considerably.

I played it through again a couple of years back, and it was easier and cheesier than I remembered, but still surprisingly magical. I actually can trace my desire to live among trees back to the first time busting into Elvandar from the caves of Mac Mordain Cadal or whatever it was.

Yes! THIS makes me so happy!

I don't typically nerd out over fantasy stuff, but I often feel so much nostalgia for this game. I was obsessed (and apparently still am the last time I tried playing) over trying to find EVERYTHING in the game, so even though it's easier and cheesier as you said, it has a surprising amount of depth, and it's still so fun to find things, characters, and places I'd forgotten about.

So many little nooks and crannies in the Dimwood! I probably would never find them all.. without DFS that is 8)