DATABASE ::: TREE TRAVERSAL

Binary Tree Traversal | Inorder, Preorder and                                    Postorder

Binary tree traversal can be done in the following ways.

Inorder traversal

Preorder traversal

postorder traversal

Consider the given binary tree,

Inorder Traversal: 7 9 4 2 5 1 3 6 8

Preorder Traversal: 1 2 4 7 9 5 3 6 8

Postorder Traversal: 9 7 4 5 2 8 6 3 1

1/5

Inorder Traversal: For binary search trees (BST), Inorder Traversal specifies the nodes in

non-descending order. In order to obtain nodes from BST in non-increasing order, a

variation of inorder traversal may be used where inorder traversal is reversed.

Preorder Traversal: Preorder traversal will create a copy of the tree. Preorder Traversal

is also used to get the prefix expression of an expression.

Postorder Traversal: Postorder traversal is used to get the postfix expression of an

expression giv

Algorithm for binary tree traversal

Inorder(root)

Traverse the left sub-tree, (recursively call inorder(root -> left).

Visit and print the root node.

Traverse the right sub-tree, (recursively call inorder(root -> right).

Preorder(root)

Visit and print the root node.

Traverse the left sub-tree, (recursively call inorder(root -> left).

Traverse the right sub-tree, (recursively call inorder(root -> right).

Postorder(root)

Traverse the left sub-tree, (recursively call inorder(root -> left).

Traverse the right sub-tree, (recursively call inorder(root -> right).

Visit and print the root node.

Program for binary tree traversals in inorder, preorder, and postorder traversals is given

below.

#include <iostream>

#include <stdlib.h>

using namespace std;

/* Structure for a node */

struct node

{i

nt data;

struct node *left;

struct node *right;

};

/* Function to create a new node */

struct node *newNode(int data)

{struct node *

temp =

(

struct node *) malloc(sizeof(struct node));

temp -> data = data;

2/5

temp -> left = NULL;

temp -> right = NULL;

return temp;

};

/* Function to insert a node in the tree */

void insert_node(struct node *root, int n1, int n2, char lr)

{i

f(root == NULL)

return;

if(root -> data == n1)

{s

witch(lr)

{c

ase 'l' :root -> left = newNode(n2);

break;

case 'r' : root -> right = newNode(n2);

break;

}}e

lse

{i

nsert_node(root -> left, n1, n2, lr);

insert_node(root -> right, n1, n2, lr);

}}

/* Function to print the inorder traversal of the tree */

void inorder(struct node *root)

{i

f(root == NULL)

return;

inorder(root -> left);

cout << root -> data << " ";

inorder(root -> right);

}

/* Function to print the preorder traversal of the tree */

void preorder(struct node *root)

{i

f(root == NULL)

return;

cout << root -> data << " ";

preorder(root -> left);

preorder(root -> right);

}

/* Function to print the postorder traversal of the tree */

void postorder(struct node *root)

{i

f(root == NULL)

return;

postorder(root -> left);

3/5

postorder(root -> right);

cout << root -> data << " ";

}

/* Main Function */

int main()

{s

truct node *root = NULL;

int n;

cout <<"\nEnter the number of edges : ";

cin >> n;

cout << "\nInput the nodes of the binary tree in order \n\nparent-child-left(or)right-\n\n";

while(n--)

{c

har lr;

int n1,n2;

cin >> n1 >> n2;

cin >>lr;

if(root == NULL)

{r

oot = newNode(n1);

switch(lr)

{c

ase 'l' :root -> left = newNode(n2);

break;

case 'r' : root -> right = newNode(n2);

break;

}}e

lse

{i

nsert_node(root,n1,n2,lr);

}}c

out <<"\nInorder Traversal : ";

inorder(root);

cout << endl;

cout <<"\nPreorder Traversal : ";

preorder(root);

cout << endl;

cout <<"\nPostorder Traversal : ";

postorder(root);

cout << endl;

return 0;

}

Output:

4/5

5/5

READ MORE BLOGS ON:- https://darkwriter17.blogspot.com