Updated March 13, 2023
Introduction to Tree traversal types
Traversal is the process of going through all nodes in the tree and printing the values. All the nodes in these trees are connected through edges. These traversal trees start from the root node, and we can traverse the tree and access the tree randomly as required. The tree has branches and subdivisions. The trees have a hierarchical structure that helps in traversing the trees. The data in these trees can be traversed in this hierarchical manner, unlike the linear data structures like an array, stacks, queues, etc. In this topic, we are going to learn about Tree traversal types.
Tree Traversal Types
In order to understand the types of tree traversals, let us first understand the components of the tree. These include:
- Root: This is the topmost node or parent node of the tree. This is where the tree will start. After that, it is connected in the direction downwards to one or more nodes present.
- Child node: This node is the node where the link will have an edge coming from the parent node. There will be an incoming link from the parent node.
- Sibling node: These nodes are adjacent nodes and share the same parent nodes.
- Leaf node: This is the node that does not have any children nodes and is usually at the base of the tree.
- Subtree: This is the part of a larger tree.
- Depth of the tree: The number of edges presents between the specified node, and the root is defined as the depth of the tree
- Height of the tree: The longest path from a particular node to the leaf node is known as the height of the tree.
Let us now have a look at the types of tree traversals.
The data structures like arrays, linked lists, queues are linear in structure, and their traversal is in a linear manner. The trees, on the other hand, are different and require the recursive way of traversal. This recursion can happen in two ways:
- Depth First Traversal
- Breadth-First Traversal
Depth First Traversal
The depth-first search chooses the approach of traversing the tree from the top of the tree to the bottom. The approach this search uses is the first in last out approach. It stacks the data structure where the node which is in the tree first will be traversed in the last. It traverses the left tree first and then followed by is the right subtree. The depth-first traversal has three types. They are as below:
- In order traversal
- Pre-order traversal
- Postorder traversal
Let us check this one by one
1. In order Traversal
In this type of traversal, we choose to first traverse the left side of the tree, visit the root and then move on to the right side of the tree. To summarise, we start with the root node, move to the left side, and traverse the subtrees present on this site recursively. The parent node and then the sibling node are traversed one by one. This is done recursively until we reach the root node, and then in a similar way, we traverse through the right side of the tree starting from the leftmost node present.
Below is an example of In order traversal of the tree
/* Creating a class with left, root and right nodes*/
class InNode {
int k;
InNode lft, rgt;
public InNode(int itm)
{
k = itm;
lft = rgt = null;
}
}
class BinTree {
// Root of Binary Tree
InNode troot;
BinTree()
{
troot = null;
}
/* Displaying the nodes in In order traversal format*/
void displayInorder(InNode node)
{
if (node == null)
return;
/* Traversing on the left child first */
displayInorder(node.lft);
/* Printing the data of the node */
System.out.print(node.k + " ");
/* Traversing on the right child */
displayInorder(node.rgt);
}
void displayInorder() { displayInorder(troot); }
public static void main(String[] args)
{
BinTree tree = new BinTree();
tree.troot = new InNode(1);
tree.troot.lft = new InNode(2);
tree.troot.rgt = new InNode(3);
tree.troot.lft.lft = new InNode(4);
tree.troot.lft.rgt = new InNode(5);
System.out.println("\nInorder traversal of binary tree is ");
tree.displayInorder();
}
}
In the above program, we have created a class first to create the left and right nodes. They both have initially null values. Next, a tree is created with a root node and keeping it null as well. Then, another function is created to display these nodes. The display function goes from left to root node to the right node. We then have the main function, which first defines an object for a binary tree. Once this object is created, values are inserted using the different class objects. Some are inserted on the left side, while some are inserted on the right side. Once these nodes are inserted, we traverse the way from left to right by calling the functions accordingly. This has been done in the display function.
The output, as seen, first traverses the left node and then goes back to the root and finally to the right side.
2. Pre-order Traversal
The pre-order traversal approach goes by levels in the tree. The order it follows is the root, left side of the tree, and then the right side of the tree. It considers the root node and then recursively traverses the left side of the tree and then the right side of the subtree.
The above code can be easily modified for first inserting and traversing first the root and then followed by the left and right sides of the tree.
3. Postorder Traversal
This is the third type of traversal in DFS. Here we traverse the left side of the tree first. Then we move on to the right side of the tree, followed by the root node in the end.
Breadth-First Search
This method traverses the tree according to the levels. By this, we mean that every node is visited from left to right and then moves down the level. Thus, each child node is traversed before we move to the next level. These next nodes will be referred to as the grandchildren.
Conclusion
We hence saw all traversal methods of trees, which can help us go through the hierarchical tree in different ways. Moreover, it can be done in a depth or breadth manner as per user and requirement needs.
Recommended Articles
This is a guide to Tree traversal types. Here we discuss the types of tree traversals along with the components of the tree. You may also have a look at the following articles to learn more –
