Tree Traversal

7 min readMar 24, 2021

What is a tree?

Before we look into tree traversal we need to know what we meant by a tree. It is a form of data structure same as stack, queue, linked list, etc. It is a nonlinear hierarchical data structure. A tree contains nodes that are connected by edges.

Tree Terminologies

Node

A node is a form of a structure that contains a value or key and acts as pointers to its child nodes. Each node has child nodes, it could be zero or more.

If a node has zero child nodes it means it is a leaf node or external node and if it has at least one child node then it is called an internal node.

Edge

The link between any two nodes is called an edge.

Root

The top node of a tree is called a root node.

Height of a Node

It is defined as the number of edges from the given node to the deepest leaf.

Depth of a Node

It is defined as the number of edges from the given root to the node.

Height of a Tree

It is defined as the depth of the leaf node or the height of the given root node.

Degree of a Node

The total number of branches of the given node is called the degree of a node.

Forest

A forest is the arrangement of disjoin trees and it is created by removing the root node of the given tree.

There are basically four types of tree Binary Tree, BST(Binary search tree), B-tree, AVL tree. We will be mostly focusing on the binary trees in this blog. A binary tree can have maximum two children for each parent node. In a binary search tree, the right subtree of a node has only nodes with values larger than the given node and the left subtree of a node has only nodes with values smaller than the given node, and also both the subtree must be Binary Search tree.

We are going to discuss basically three types of traversals below i.e inorder, preorder, and postorder traversal.

Inorder traversal

Steps for doing inorder traversal are as follows:-

First, traverse the left subtree.
Then visit the root.
At last traverse the right subtree.

I am going to explain inorder traversal with an example. A lot of us usually get confused between inorder and postorder traversal. Let’s take this image as an example and we need to find out the inorder traversal of this tree.

We will first start a recursive call from the root node i.e 30 here and then we will move to all the left children of the root node so first, we go to 20 then 15 then 5.
As 5 is a leaf node(no child present) so our first element in our inorder traversal will be 5 and after that, we move on to the parent node which is 15 here, so our second element is 15 and then we go to the right child i.e 18 here.
As 18 is a leaf node(no child present) so 18 is our next element and then we will go to 20 after that we will go to the right child of 20 i.e 25 here .25 has no child so it’s our next element in our inorder traversal.
Then we came to root node 30 and print it.
Now in the same way we will recursively traverse the right subtree. We go to 40. 40 has left subtree.
40 has only one left node i.e 35 and 35 doesn’t have any subtree so our next element to print is 35 and then we go to parent node i.e 40 and print it.
Now we will traverse the right subtree of the parent node. First, we will go to the left child of 50 i.e 45. As 45 has no child so our next element to print is 45.
Then we again came back to the parent node i.e 50 and we will print it. Then we will traverse the right subtree of 50. As here right child of 50 i.e 60 has no child so our next and final element to print is 60.
Our final answer will be 5,15,18,20,25,30,35,40,45,50,60.

Preorder Traversal

Steps for doing preorder traversal are as follows:-

First, visit the root.
Then traverse the left subtree.
At last traverse the right subtree.

I am going to explain preorder traversal with an example. A lot of us usually get confused between inorder and postorder traversal. Let’s take this image as an example and we need to find out the preorder traversal of this tree.

We will first start with the topmost node i.e root node 30. So 30 will be our first element and after that, we will recursively traverse the left subtree.
So our next value will be 20, as we can see 20 also has subtree so our next element to print will be 20 and we will traverse to the left subtree of 20.
Our next value will be 15, as we can see 15 also has a subtree so our next element to print will be 15 and we will traverse to the left subtree of 15.
Our next element to print will be 5 s it has no subtree and now we will traverse to the right subtree of 15.
So our next value will be 18 as it has no child we will print it and we will traverse to the right subtree of 20.
So our next value will be 25 as it has no child we will print it and we will traverse to the right subtree of 30.
Now we will go to node 40 as it has a subtree, first, we will print 40, and then afterward we will traverse to the left subtree of 40.
So our next value will be 35 as 35 has no subtree we will print it and we will traverse to the right subtree of 40.
Now we will go to node 50 as it has a subtree, first, we will print 50, and then afterward we will traverse to the left subtree of 50.
So our next value will be 45 as it has no subtree we will print it and we will move to node 60 and print our final element.
Our final answer will be 30 , 20 , 15 , 5 , 18 , 25 , 40 , 35 , 50 , 45 , 60.

Postorder Traversal

Steps for doing postorder traversal are as follows:-

First, traverse the left subtree.
Then traverse the right subtree.
At last visit the node.

I am going to explain postorder traversal with an example. A lot of us usually get confused in the postorder traversal. Let’s take this image as an example and we need to find out the postorder traversal of this tree.

We will first start with the root node and following the above steps, we will traverse the left subtree. First, we go to 20 then 15, then we will go to 5. As it has no subtree, we will print it and now we will traverse to the right subtree of 15.
As 18 is a right subtree of 15 and it has no child, so our next element to print will be 18 and then we will come to the parent node i.e 15 and we will print it.
Now we will go to the right subtree of 20, as 25 has no subtree we will first print 25 and then 20.
Now we will go to a right subtree of 30 which is 40 as 40 has a subtree so first, we will go to the left subtree i.e to 35. As 35 has no subtree we will print it and then we will traverse the right subtree of 40.
So now we will move to 50(as it is the right subtree of 40). As it has a subtree so first, we will go to the left subtree which is 45. As it has no subtree we will print it and then we will print 60 which is the right subtree of 50. Afterward, we will print 50.
Now we will move to 40 and print it. Following a similar process, we will move to 30 and print it.
our final answer will be 5 , 18 , 15 , 25 , 20 , 35 , 45 , 60 , 50 , 40 , 30.