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

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!

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

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.

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.

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!

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

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:

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

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:

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

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!

• Part 1 - The Basics
• Part 2 - Binary Search Trees (Insertion and Search)
• Part 3 - Node Deletion
• Part 5 - Breadth-First Traversals