Tree Traversal Techniques in the data structure is methods to visit or traverse every node of the tree.

Tree traversal techniques

What is Tree Traversal?: Traversing tree means visiting all its nodes to get the complete tree information. We visit each node of the tree starting from the root node and visit each node connected to the root node until the Leaf node.
In the data structure, there are different Tree traversal techniques to traverse the tree.

Tree traversal methods

There are three methods of tree traversal

  1. Preorder
  2. Inorder
  3. Postorder

Let’s see tree traversal methods one by one

1. Preorder traversal

This is the first method of tree traversal in a data structure.
In this method we first visit the root node, next we visit all left subtree and at last, we visit the right sub tree.

Preorder traversal algorithm
  1. Visit root
  2. Traverse the left sub tree in Preorder
  3. Traverse right sub tree in Preorder

2. Inorder traversal

This is the second method of tree traversal in a data structure.
In this method we first visit all left sub tree, next we visit the root node, and at last, we visit the right sub tree.

Inorder traversal algorithm
  1. Traverse the left sub tree in inorder
  2. Visit root
  3. Traverse the right sub tree in inorder

3. Postorder traversal

This is the third method of tree traversal in the data structure.
In this method we first visit all left sub tree, next we visit right sub tree, and at last visit root node.

Preorder traversal algorithm
  1. Traverse left sub tree in post order
  2. Traverse right sub tree in post order
  3. Visit root

Tree traversal example

Tree Traversal Techniques
Tree Traversal Techniques

Consider above tree with A,B,D,E,F,G nodes of tree.
Let us traverse the tree using tree traversal methods in a data structure.
Preorder traversal = A B E G D F
Inorder traversal = E B G A F D
Postorder traversal = E G B F D A

Tree traversal algorithm

  1. Create a structure to store tree value and left and right pointer.
  2. Write Function to inorder traversal
  3. Write a function for preorder traversal
  4. Similarly write function for postorder traversal.
  5. Create a nodes of tree dynamically and arrange in tree.
  6. Traverse tree using tree traversal method

Tree Traversal program in c

#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node* left;
struct node* right;
};

void inorder(struct node* root){
if(root == NULL) return;
inorder(root->left);
printf("%d ->", root->data);
inorder(root->right);
}

void preorder(struct node* root){
if(root == NULL) return;
printf("%d ->", root->data);
preorder(root->left);
preorder(root->right);
}

void postorder(struct node* root) {
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ->", root->data);
}


struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

struct node* insertLeft(struct node *root, int value) {
root->left = createNode(value);
return root->left;
}


struct node* insertRight(struct node *root, int value){
root->right = createNode(value);
return root->right;
}


int main(){
struct node* root = createNode(1);
insertLeft(root, 12);
insertRight(root, 9);

insertLeft(root->left, 5);
insertRight(root->left, 6);

printf("Inorder traversal \n");
inorder(root);

printf("\nPreorder traversal \n");
preorder(root);

printf("\nPostorder traversal \n");
postorder(root);
}

Output :
Tree

Write A Comment