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