Nerd For Tech
Published in

Nerd For Tech

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.

Find more amazing visualization tools like this one at https://visualgo.net/en/bst

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.

--

--

--

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Recommended from Medium

How to paginate with Laravel — Very easy!

Public Alpha Release 1

Cyber Roos Whitepaper

Calculator Program in Python

No Code, FLAIR, Object Storage; ThDPTh #62

Patreon + Fun Fun Forum launch

BollyCoin - Update March 22nd 2022

5 Common Mistakes UiPath RPA Developers Should Avoid

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Liam Hanafee-Areces

Liam Hanafee-Areces

More from Medium

Snake and Ladder with Graphs

What is recursion?

Shower thoughts on ways to cheat with algorithm time complexity

Assembly Line Scheduling