Learning Tree Traversal
Another week into studying data structures and algorithms, I am learning about tree traversal. Last week, I wrote a blog about my introduction to binary search trees, which can be found here. That article is an overview of what trees are, and how to construct them with JavaScript classes. This article will expand that same class, which can be found here, to include some of the more common algorithms for tree traversal.
Tree traversal is a classic computer science problem. The idea is to visit every single node in the tree once, regardless of the shape or specific type of tree. There are many ways of doing it, and each can be good in different situations. This is much different from a Linked List, Stack, or Queue, where there is really just one way of visiting every node, and that is to go from the beginning to the end in a linear manner.
There are two main ways of traversing a tree. The first is called Breadth-First Search(BFS), and the second is called Depth-First Search(DFS). BFS works “across” the tree, visiting each nodes siblings before moving on to their children, while DFS visits a node’s child nodes before its sibling nodes. They both have the same time complexity, but sometimes one will be better than the other depending on the specific scenario.
Breadth-First Search
BFS starts by visiting the root node, then going to the next level below from left to right. Once it visits the sibling node that is furthest on the right of a level, it goes to the next level and repeats the process until all nodes have been visited. In order to know which node to visit once it needs to go down a level in the tree, a BFS algorithm has to store nodes in a queue or array. This means that on particularly wide trees, BFS is not a great choice since so many nodes have to be stored in memory. In the example below, I wrote a BFS algorithm using an array instead of a queue for simplicity’s sake, although a queue would be more performant.
There are some situations where BFS performs well. For example, if we are traversing a tree where each node only has one child, only one node needs to be stored in the queue at once, so not too much memory will be needed.
Depth-First Search
There are a few variants of DFS, but one thing that they have in common is that all of them visit a node’s children before it’s siblings. The main variants are called Inorder, Preorder, and Postorder.
Inorder
Inorder visits nodes in order of ascending value, which can be useful if you need the data to be returned sorted in that manner.
Preorder
Preorder visits the root, then descends down the left side of the tree before moving over to the right side.
Postorder
Postorder visits the node at the bottom left of the tree, it’s siblings, and then moves up towards the parents. Once the left side of the tree has been visited, it visits the bottom right and repeats the same process as on the left. Finally, it goes back and visits the root node last.
