Scribd
Upload
28 views15 pages

05-Tree Traversals

The document discusses tree traversal methods in data structures, specifically focusing on inorder, preorder, and postorder traversals. Each traversal method is explained with its respective algorithm and examples, demonstrating how they process nodes in a binary tree. Additionally, the document provides recursive routines for implementing these traversal methods in code.

Uploaded by

Bhuvan Balan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views15 pages

05-Tree Traversals

The document discusses tree traversal methods in data structures, specifically focusing on inorder, preorder, and postorder traversals. Each traversal method is explained with its respective algorithm and examples, demonstrating how they process nodes in a binary tree. Additionally, the document provides recursive routines for implementing these traversal methods in code.

Uploaded by

Bhuvan Balan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures and Algorithms

Tree
Traversals

[Link], AP (SG) / CSE


9791519152
bhuvaneswaran@[Link]
Introduction
 The process of visiting all nodes of a tree is called tree traversal.
 Each node is processed only once but it may be visited more than
once.

Tree Traversals Rajalakshmi Engineering College 2


Types of Tree Traversal
 Inorder traversal
 Preorder traversal
 Postorder traversal

Tree Traversals Rajalakshmi Engineering College 3


Inorder Traversal
 The inorder traversal of a binary tree is performed as:
• Traverse the left subtree in inorder
• Visit the root
• Traverse the right subtree in inorder
 The inorder traversal of the binary tree for an arithmetic
expression gives the expression in an infix form.

Tree Traversals Rajalakshmi Engineering College 4


Example
 ABCDEGHIJK

Tree Traversals Rajalakshmi Engineering College 5


Recursive Routine: Inorder Traversal
void Inorder(Node *Tree)
{
if (Tree != NULL)
{
Inorder(Tree->left);
printf("%d\t", Tree->element);
Inorder(Tree->right);
}
}

Tree Traversals Rajalakshmi Engineering College 6


Preorder Traversal
 The preorder traversal of a binary tree is performed as:
• Visit the root
• Traverse the left subtree in preorder
• Traverse the right subtree in preorder
 The preorder traversal of the binary tree for the given expression
gives in prefix form.

Tree Traversals Rajalakshmi Engineering College 7


Example
 DCABIGEHKJ

Tree Traversals Rajalakshmi Engineering College 8


Recursive Routine: Preorder Traversal
void Preorder(Node *Tree)
{
if (Tree != NULL)
{
printf("%d\t", Tree->element);
Preorder(Tree->left);
Preorder(Tree->right);
}
}

Tree Traversals Rajalakshmi Engineering College 9


Postorder Traversal
 The postorder traversal of a binary tree is performed by:
• Traverse the left subtree in postorder
• Traverse the right subtree in postorder
• Visit the root
 The postorder traversal of the binary tree for the given expression
gives in postfix form.

Tree Traversals Rajalakshmi Engineering College 10


Example
 BACEHGJKID

Tree Traversals Rajalakshmi Engineering College 11


Recursive Routine:Postorder Traversal
void Postorder(Node *Tree)
{
if (Tree != NULL)
{
Postorder(Tree->left);
Postorder(Tree->right);
printf("%d\t", Tree->element);
}
}

Tree Traversals Rajalakshmi Engineering College 12


Example
 Traverse the given tree using inorder, preorder and postorder
traversals.

Tree Traversals Rajalakshmi Engineering College 13


Example
 Inorder
• A+B*C–D/E
 Preorder
• *+AB–C/DE
 Postorder
• AB+CDE/-*

Tree Traversals Rajalakshmi Engineering College 14


Thank You

You might also like