Binary
Tree Traversal
The traversal is a process of visiting all the nodes of a tree and may print their values too. All the nodes in the tree are connected through the edges. We always start from the root node of the tree, which means we cannot access the tree randomly from any node. There are three ways which we use to traverse the tree. They are
Generally, the binary tree is traversed to search or locate an element or to print the all the elements it contains.
In-order Traversal
In the traversal, the left subtree
is visited first, then the root and later the right subtree. We should always
remember that every node represent the subtree itself.
The main advantage of in-order traversal is that the element is always printed in sorted ascending order.
From the above figure, we could see that,
Finally, the in-order traversal for the above binary tree will be,
D->B->E->A->F->C->G
Algorithm
Step 1: Recursively
traverse the left subtree in-order.
Step 2: Visit root
node.
Step 3: Recursively traverse the right subtree in-order.
Uses:
Pre-order Traversal
In this traversal method, the root
is traversed first, then the left subtree and finally, the right subtree.
Here in pre-order traversal, we
start traversing from the root node A,
then move to left subtree B, whereas B is also traversed in pre-order.
This process is continued until all the nodes are visited. The following is the
output for pre-order traversal of the above tree:
A->B->D->E->C->F->G
Algorithm
Step 1: Visit the root
node.
Step 2: Recursively
traverse the left subtree in-order.
Step 3: Recursively traverse the right subtree in-order.
Uses:
Post-order Traversal
In this traversal method, the root node is visited last. First we traverse the left subtree, then right subtree and finally the root node.
We start from A, following
post-order traversal, we first visit the left subtree B and then the right
subtree C. B is also traversed post-order and C also traversed post-order. The
following is the post-order traversal of the above tree:
D->E->B->F->G->C->A
Algorithm
Step 1: Recursively
traverse the left subtree in-order.
Step 2: Recursively
traverse the right subtree in-order.
Step 3: Visit the root
node.
Uses:
The following is the C code implementation of tree traversal:
+91-4446311234
+1-6502652492
+91-7530088009
// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* This method allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct node* node)
{
if (node == NULL)
return;
// Recursively call left subtree
printPostorder(node->left);
// Recursively call right subtree
printPostorder(node->right);
// Deal with the node
printf("%d ", node->data);
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
// Recursively call left subtree
printInorder(node->left);
//Print the node data
printf("%d ", node->data);
// Recursively call right subtree
printInorder(node->right);
}
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct node* node)
{
if (node == NULL)
return;
// Print the node data
printf("%d ", node->data);
// Recursively call left subtree
printPreorder(node->left);
// Recursively call right subtree
printPreorder(node->right);
}
// Main function which drive all the above functions
int main()
{
struct node *root = newNode(5);
root->left = newNode(3);
root->right = newNode(8);
root->left->left = newNode(1);
root->left->right = newNode(4);
root->right->left = newNode(7);
root->right->right = newNode(9);
printf("\nPre-order traversal of binary tree is \n");
printPreorder(root);
printf("\nIn-order traversal of binary tree is \n");
printInorder(root);
printf("\nPost-order traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
Output:
Pre-order traversal of binary tree is 5 3 1 4 8 7 9 In-order traversal of binary tree is 1 3 4 5 7 8 9 Post-order traversal of binary tree is 1 4 3 7 9 8 5
