Binary Tree Traversal Algorithms | DFS | Algorithm

There are three Depth First Search (DFS) types of traversal algorithms for Binary Tree. Traversal algorithms are for traversing in a Binary Tree. These three are variations of the Depth First Search (DFS) algorithm. In DFS, we start traversing from the root and go in-depth until there is no node to traverse. Its uses in Tree and Graph related data structures. But this time, ignore the graph-related thinking.

Tree
Binary Tree

Let’s try to understand how these three traversal algorithms work.

Inorder Traversal

In an inorder traversal algorithm, we follow the DFS basic rule. And also an extra pretty simple rule for inorder traversal algorithm only. That means the way or order we will follow to go through the binary tree.

• Left (Left Subtree)
• Node
• Right (Right Subtree)

It’s a pretty simple rule. To get a clear understanding, let’s use this rule to print all nodes of a binary tree. Consider the following binary tree.

						             1
					              /      \
                                2          3
                              /   \      /    \
                             4     5    6      7

To print all nodes, we will follow the above three points. For that, we will start traversing from the root and recursively traverse to the left node until there are no node exists, and then visit (print) the node. At this point, our output will be 4 (left-node). And then start traversing to the right side. But at this point, the right is null (left-node-right). So we will return to node 2. The left of 2 is already visited. Now we can print node 2. After that, go to the right child of it, and follow the same rule.

We will continue this way until all of our nodes are getting printed. Output will be: 4, 2, 5, 1, 6, 3, 7.

Postorder Traversal

In the same way, we can think of the postorder algorithm. The only difference is in the ordering. The rule for postorder traversal algorithm is:

• Left (Left Subtree)
• Right (Right Subtree)
• Node

						             1
					              /      \
                                2          3
                              /   \      /    \
                             4     5    6      7

Let’s apply this algorithm to the above binary tree. The output will be 4, 5, 2, 6, 7, 3, 1.

First, we will recursively go to the leftmost node until there is no node to traverse, that is, 4. And left of 4 is null, and the right is also the same. As per the rule, now we can visit 4. After that, go to the right side, and this time it’s 5. And there are nothing to traverse left and right of this node. So we can visit 5. Now go the node 2, and both sides of this node are already visited. So we can print 2. This way, we can go to 3 and so on.

Preorder Traversal

If you already understand how the other traversal algorithm works, it will not be a big deal to understand preorder traversal. It works the same way, but the ordering is different. The rule for preorder traversal is:

• Node
• Left (Left Subtree)
• Right (Right Subtree)

						             1
					              /      \
                                2          3
                              /   \      /    \
                             4     5    6      7

Let’s apply this algorithm to the above binary tree. The output will be 1, 2, 4, 5, 3, 6, 7.

Code

We can implement this algorithm in code using both iterative and recursive ways.

Click on the following link to see the code (Python) implementation of these three algorithms in iterative and recursive ways.

• Iterative
• Recursive

This blog is a very minimal overview of three Binary Tree algorithms. I hope this blog will help you to understand these basics.

Tags: Binary TreeDFSTreeTree Traversal