Unlike linear data structures (Array, Linked List, Queues,
Stacks, etc) which have only one logical way to traverse them, trees can
be traversed in different ways. Following are the generally used ways
for traversing trees.
Example Tree
Depth First Traversals:
(a) Inorder
(b) Preorder
(c) Postorder
Breadth First or Level Order Traversal
Please see this post for Breadth First Traversal.
Inorder Traversal:
Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Uses of Inorder
In case of binary search trees (BST), Inorder traversal gives nodes in
non-decreasing (Increasing) order.
Lets say we have BInary Search Tree as Below
4
/ \
/ \
2 7
Inorder Traversal Gives 2 , 4 and 7.
To get nodes of BST in non-increasing order, a
variation of Inorder traversal where
Inorder itraversal s reversed, can
be used.
Example: Inorder traversal for the above given figure is 4 2 5 1 3.
Preorder Traversal:
Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Uses of Preorder
Preorder traversal is used to create a copy of the tree.
Preorder
traversal is also used to get prefix expression on of an expression
tree.
Please see http://en.wikipedia.org/wiki/Polish_notation to know why prefix expressions are useful.
Example: Preorder traversal for the above given figure is 1 2 4 5 3.
Postorder Traversal:
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
Uses of Postorder
Postorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree.
Example: Postorder traversal for the above given figure is 4 5 2 3 1.
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
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);
}
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct node* node)
{
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
printf("%d ", node->data);
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Given a binary tree, print its nodes in inorder*/
void printPreorder(struct node* node)
{
if (node == NULL)
return;
/* first print data of node */
printf("%d ", node->data);
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
/* Driver program to test above functions*/
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("\n Preorder traversal of binary tree is \n");
printPreorder(root);
printf("\n Inorder traversal of binary tree is \n");
printInorder(root);
printf("\n Postorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
Iterative Preorder Traversal
To convert an inherently recursive procedures to iterative, we need an explicit stack .
Following is a simple stack based iterative process to print Preorder traversal.
1) Create an empty stack nodeStack and push root node to stack.
2) Do following while nodeStack is not empty.
….a) Pop an item from stack and print it.
….b) Push right child of popped item to stack
….c) Push left child of popped item to stack
Sample Code :
|
// An iterative process to print preorder traversal of Binary tree
void iterativePreorder(node *root)
{
// Base Case
if (root == NULL)
return;
// Create an empty stack and push root to it
stack<node *> nodeStack;
nodeStack.push(root);
/* Pop all items one by one. Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first so that left is processed first */
while (nodeStack.empty() == false)
{
// Pop the top item from stack and print it
struct node *node = nodeStack.top();
printf ("%d ", node->data);
nodeStack.pop();
// Push right and left children of the popped node to stack
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
}
Iterative Inorder Traversal :
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
Let us consider the below tree for example
1
/ \
2 3
/ \
4 5
Step 1 Creates an empty stack: S = NULL
Step 2 sets current as address of root: current -> 1
Step 3 Pushes the current node and set current = current->left until current is NULL
current -> 1
push 1: Stack S -> 1
current -> 2
push 2: Stack S -> 2, 1
current -> 4
push 4: Stack S -> 4, 2, 1
current = NULL
Step 4 pops from S
a) Pop 4: Stack S -> 2, 1
b) print "4"
c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.
Step 4 pops again.
a) Pop 2: Stack S -> 1
b) print "2"
c) current -> 5/*right of 2 */ and go to step 3
Step 3 pushes 5 to stack and makes current NULL
Stack S -> 5, 1
current = NULL
Step 4 pops from S
a) Pop 5: Stack S -> 1
b) print "5"
c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything
Step 4 pops again.
a) Pop 1: Stack S -> NULL
b) print "1"
c) current -> 3 /*right of 5 */
Step 3 pushes 3 to stack and makes current NULL
Stack S -> 3
current = NULL
Step 4 pops from S
a) Pop 3: Stack S -> NULL
b) print "3"
c) current = NULL /*right of 3 */
Traversal is done now as stack S is empty and current is NULL.
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;
while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}
/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}
Iterative Post order Traversal :
Iterative postorder traversal is discussed which is more complex than the other two traversals (due to its nature of non-tail recursion, there is an extra statement after the final recursive call to itself).
The postorder traversal can easily be done using two stacks though. The idea is to push reverse postorder traversal to a stack. Once we have reverse postorder traversal in a stack, we can just pop all items one by one from the stack and print them, this order of printing will be in postorder because of LIFO property of stacks.
Now the question is, how to get reverse post order elements in a stack – the other stack is used for this purpose. For example, in the following tree, we need to get 1, 3, 7, 6, 2, 5, 4 in a stack. If take a closer look at this sequence, we can observe that this sequence is very similar to preorder traversal.
The only difference is right child is visited before left child and therefore sequence is “root right left” instead of “root left right”.
So we can do something like iterative preorder traversal with following differences.
a) Instead of printing an item, we push it to a stack.
b) We push left subtree before right subtree.
Following is the complete algorithm.
After step 2, we get reverse postorder traversal in second stack.
We use first stack to get this order.
1. Push root to first stack.
2. Loop while first stack is not empty
2.1 Pop a node from first stack and push it to second stack
2.2 Push left and right children of the popped node to first stack
3. Print contents of second stack
Following are the steps to print postorder traversal of the above tree using two stacks.
1. Push 1 to first stack.
First stack: 1
Second stack: Empty
2. Pop 1 from first stack and push it to second stack.
Push left and right children of 1 to first stack
First stack: 2, 3
Second stack: 1
3. Pop 3 from first stack and push it to second stack.
Push left and right children of 3 to first stack
First stack: 2, 6, 7
Second stack:1, 3
4. Pop 7 from first stack and push it to second stack.
First stack: 2, 6
Second stack:1, 3, 7
5. Pop 6 from first stack and push it to second stack.
First stack: 2
Second stack:1, 3, 7, 6
6. Pop 2 from first stack and push it to second stack.
Push left and right children of 2 to first stack
First stack: 4, 5
Second stack:1, 3, 7, 6, 2
7. Pop 5 from first stack and push it to second stack.
First stack: 4
Second stack: 1, 3, 7, 6, 2, 5
8. Pop 4 from first stack and push it to second stack.
First stack: Empty
Second stack: 1, 3, 7, 6, 2, 5, 4
// An iterative function to do post order traversal of a given binary tree
void postOrderIterative(struct Node* root)
{
// Create two stacks
struct Stack* s1 = createStack(MAX_SIZE);
struct Stack* s2 = createStack(MAX_SIZE);
// push root to first stack
push(s1, root);
struct Node* node;
// Run while first stack is not empty
while (!isEmpty(s1))
{
// Pop an item from s1 and push it to s2
node = pop(s1);
push(s2, node);
// Push left and right children of removed item to s1
if (node->left)
push(s1, node->left);
if (node->right)
push(s1, node->right);
}
// Print all elements of second stack
while (!isEmpty(s2))
{
node = pop(s2);
printf("%d ", node->data);
}
}
With Single Stack :
The idea is to move down to leftmost node using left pointer. While
moving down, push root and root’s right child to stack. Once we reach
leftmost node, print it if it doesn’t have a right child. If it has a
right child, then change root so that the right child is processed
before.
Following is detailed algorithm.
1.1 Create an empty stack
2.1 Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
