Tree Traversal data structure
Tree Traversal data structure
Tree traversal data structure is process for visiting the nodes in some order. Enumeration of the tree node is defined as any travrsal that lists every node in the tree exactly once. Ordered tree are often used to store information.
There are three types to traversing the tree they are follows:
-
- Inorder traversal
- Preorder traversal
- Postorder traversal
1. Inorder Traversal
The following is a recursive algorithm for an inorder traversal of the tree that prints the contents of each node when it is visited. This function is invoked by the call inorder (root).
In inorder First, visit all the nodes in the left subtree then the root node and at last visit all the nodes in the right subtree
Algorithm of Inorder Traversal
1. Traverse the left subtree) 2. Visit the root. 3. Traverse the right subtree
Example of inorder traversal
Inorder traveral of above tree is
Inorder : 4 2 5 1 3
2. Preorder Traversal
The following is a recursive algorithm for an inorder traversal of the tree that prints the contents of each node when it is visited. This function is invoked by the call preorder (root).
In preorder first visit root node then visit all the nodes in the left subtree and last visit all the nodes in the right subtree
Algorithm of preorder traversal
1. Visit the root. 2. Traverse the left subtree 3. Traverse the right subtree
Example of preorder traversal
Preorder traversal of above tree is
Preorder : 1 2 4 5 3
3. Postorder Traversal
The following is a recursive algorithm for an inorder traversal of the tree that prints the contents of each node when it is visited. This recursive function is invoked by the call postorder (root).
In postorder firstly, visit all the nodes in the left subtree after that visit all the nodes in the right subtree and last visit the root node
Algorithm of postorder traversal
1. Traverse the left subtree 2. Traverse the right subtree 3. Visit the root.
Example of postorder traversal
Postorder traversal of above tree is
Postorder: 4 5 2 3
Program in traversal in C
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
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);
}
//postorder traversal.
void printPostorder(struct node* node)
{
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
printf("%d ", node->data);
}
//Inorder traversal//
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
//preorder traversal
void printPreorder(struct node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("\nPreorder traversal is \n");
printPreorder(root);
printf("\nInorder traversal is \n");
printInorder(root);
printf("\nPostorder traversal is \n");
printPostorder(root);
getchar();
return 0;
}
Output
Preorder traversal is 1 2 4 5 3 Inorder traversal is 4 2 5 1 3 Postorder traversal is 4 5 2 3 1
Program of traversal in C++
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// postorder traversal.
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
cout << node->data << " ";
}
// inorder traversal
void printInorder(struct Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
// preorder traversal
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
cout << node->data << " ";
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "\nPreorder traversal is \n";
printPreorder(root);
cout << "\nInorder traversal is \n";
printInorder(root);
cout << "\nPostorder traversal is \n";
printPostorder(root);
return 0;
}
Output
Preorder traversal is 1 2 4 5 3 Inorder traversal is 4 2 5 1 3 Postorder traversal is 4 5 2 3 1
Program of traversal in python
#class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
# inorder tree traversal
def printInorder(root):
if root:
printInorder(root.left)
print(root.val),
printInorder(root.right)
# postorder tree traversal
def printPostorder(root):
if root:
# First recur on left child
printPostorder(root.left)
# the recur on right child
printPostorder(root.right)
# print the data of node
print(root.val),
# preorder tree traversal
def printPreorder(root):
if root:
# First print the data of node
print(root.val),
# Then recur on left child
printPreorder(root.left)
# Finally recur on right child
printPreorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print "Preorder traversal is"
printPreorder(root)
print "\nInorder traversal is"
printInorder(root)
print "\nPostorder traversal is"
printPostorder(root)
Output
Preorder traversal is 1 2 4 5 3 Inorder traversal is 4 2 5 1 3 Postorder traversal is 4 5 2 3 1
Program of traversal in java
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root = null; }
//postorder
void printPostorder(Node node)
{
if (node == null)
return;
printPostorder(node.left);
printPostorder(node.right);
System.out.print(node.key + " ");
}
// inorder traversal
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(node.key + " ");
printInorder(node.right);
}
// preorder traversal
void printPreorder(Node node)
{
if (node == null)
return;
System.out.print(node.key + " ");
printPreorder(node.left);
printPreorder(node.right);
}
void printPostorder() { printPostorder(root); }
void printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println(
"Preorder traversal is ");
tree.printPreorder();
System.out.println(
"\nInorder traversal is ");
tree.printInorder();
System.out.println(
"\nPostorder traversal is ");
tree.printPostorder();
}
}
Output
Preorder traversal is 1 2 4 5 3 Inorder traversal is 4 2 5 1 3 Postorder traversal is 4 5 2 3 1
Read more, Tree Data Structure
