Tree Traversals (pre‐order, post‐order and in‐order)

Tree traversals (pre-order, post-order and in-order)

A binary tree is defined recursively: it consists of a root, a left subtree, and a right subtree.

To traverse (or walk) the binary tree is to visit each node in the binary tree exactly once.

Three recursive techniques is used for binary tree traversal. In each technique, the left subtree is traversed recursively, the right subtree is traversed recursively, and the root is visited.

Three techniques are:

1. Pre-order
2. Post-order
3. In-order

In Preorder, the root is visited before left & right subtrees traversals.

In Inorder, the root is visited in-between left and right subtree traversal.

In Postorder, the root is visited after the left and right subtree traversal.

Preorder, Postorder and Inorder Traversals

Algorithm: Postorder(x)

Input: x is the root of a subtree

If x != NULL

then Postorder(left(x));

Postorder(right(x));

output key(x);

Algorithm: Postorder(x)

Input: x is the root of a subtree

if x != NULL

then Postorder(left(x));

Postorder(right(x));

output key(x);

Algorithm: Inorder(x)

Input: x is the root of a subtree

if x != NULL

then Inorder(left(x));

output key(x));

Inorder(right(x));

Example for Traversals

Preorder : 15 8 2 6 3 7 11 10 12 14 20 27 22 30

Inorder : 2 2 6 7 8 10 11 12 14 15 20 22 27 30

Postorder: 3 7 6 2 10 14 12 11 8 22 30 27 20 15

Preorder : 1 3 5 4 6 7 8 9 10 11 12

Inorder : 4 5 6 3 1 8 7 9 11 10 12

Postorder: 4 6 5 3 8 11 12 10 9 7 1

Preorder : ABCEIFJDGHKL

Inorder : EICFJBGDKHLA

Postorder: IEJFCGKLHDBA

Traversal Techniques Implementation in C

void PreOrder( Tree* tree){

if (tree != NULL){

printf(“\t %d”, tree->data);

PreOrder(tree->left);

PreOrder(tree→right);

}

}

void InOrder( Tree* tree){

if (tree != NULL){

InOrder(tree->left);

printf(“\t %d”, tree->data);

InOrder(tree→right);

}

}

void PostOrder( Tree* tree){

if (tree != NULL){

PostOrder(tree->left);

PostOrder(tree→right);

printf(“\t %d”, tree->data);

}

}

References:

1. Karumanchi, N. "Data Structures and Algorithms Made Easy"

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”