Following code illustrates various binary tree traversal algorithms - both recursively and iteratively. All algorithms provided below are DFS algorithms.
Time Complexity: O(n) - for all algorithms
/* recursive pre order traversal */
void pre_order_traversal_recursive(tree2 *t)
{
if (t == NULL) {
return;
}
/* process node here */
printf ("%d ", t->data);
pre_order_traversal_recursive(t->left);
pre_order_traversal_recursive(t->right);
}
/* recursive in order traversal */
void in_order_traversal_recursive(tree2 *t)
{
if (t == NULL) {
return;
}
in_order_traversal_recursive(t->left);
/* process node here */
printf ("%d ", t->data);
in_order_traversal_recursive(t->right);
}
/* recursive post order traversal */
void post_order_traversal_recursive(tree2 *t)
{
if (t == NULL) {
return;
}
post_order_traversal_recursive(t->left);
post_order_traversal_recursive(t->right);
/* process node here */
printf ("%d ", t->data);
}
/* iterative pre order traversal */
void pre_order_traversal_iterative(tree2 *t)
{
while (t) {
/* condition to control type of traversal */
if (((t->left && !t->left->visited) || !t->left) &&
((t->right && !t->right->visited) || !t->right)) {
/* process node here */
printf("%d ", t->data);
}
/* actual tree traversal */
if (t->left && !t->left->visited) {
t = t->left;
} else if (t->right && !t->right->visited) {
t = t->right;
} else {
t->visited = 1;
t = t->parent;
}
}
}
/* iterative in order traversal */
void in_order_traversal_iterative(tree2 *t)
{
while (t) {
/* condition to control type of traversal */
if (((t->left && t->left->visited) || !t->left) &&
((t->right && !t->right->visited) || !t->right)) {
/* process node here */
printf("%d ", t->data);
}
/* actual tree traversal */
if (t->left && !t->left->visited) {
t = t->left;
} else if (t->right && !t->right->visited) {
t = t->right;
} else {
t->visited = 1;
t = t->parent;
}
}
}
/* iterative post order traversal */
void post_order_traversal_iterative(tree2 *t)
{
while (t) {
/*
** Following condition controls the type of tree traversal
** PRE ORDER : !t->left->visited and !t->right->visited
** IN ORDER : t->left->visited and !t->right->visited
** POST ORDER : t->left->visited and t->right->visited
*/
if (((t->left && t->left->visited) || !t->left) &&
((t->right && t->right->visited) || !t->right)) {
/* process node here */
printf("%d ", t->data);
}
/* actual tree traversal */
if (t->left && !t->left->visited) {
t = t->left;
} else if (t->right && !t->right->visited) {
t = t->right;
} else {
t->visited = 1;
t = t->parent;
}
}
}
Please note that recursive algorithm will also work on regular tree data structure (i.e. without parent and visited). However, iterative algorithms only works with following data structure:
typedef struct tree2_s {
u32 data;
struct tree2_s *left;
struct tree2_s *right;
struct tree2_s *parent;
u32 visited;
} tree2;
