Tree Traversal

In our previous sections we have constructed binary trees. Now we want to visit each of the nodes in a tree and print the values one by one. The process of visiting node of a tree is known as Tree-I Iteration or Tree enumeration or Tree Traversal. There are several common orders in which the nodes can be visited, and each has practical implications. There are broadly three types of Tree Traversal logics available:
  • Pre-Order
  • In-Order
  • Post-Order

Pre-Order

Visit Root then Visit Left child and then Right child.

Pre-Order Traversal

void pre_order (struct node* node) { 
  if (node == NULL) { 
    return; 
  } else {
    printf ("%d", node->value);
    pre_order (node->left);
    pre_order (node->right); 
  } 
}
10 

In-Order

Visit Left child, then Visit Root, and Visit Right child.

In-Order Traversal

void in_order (struct node* node) { 
  if (node == NULL) { 
    return; 
  } else {
    in_order (node->left);
    printf ("%d", node->value);
    in_order (node->right); 
  } 
}
10 

Post-Order

Visit Left Child, Visit Right child, then Visit Root.

Post-Order Traversal

void post_order (struct node* node) { 
  if (node == NULL) { 
    return; 
  } else {
    post_order (node->left);
    post_order (node->right); 
    printf ("%d", node->value);
  } 
}
10 

Depth-first Search Order

Depth-first order visit root and iterate immediately till the depth of the child tree without visiting same level nodes. Recursion is used to do this iteration. There is no need to remember same level nodes as we call recursively for each child starting from root. This iteration takes a child of root visits entire sub tree till leaf node and further takes another child and completes entire depth and in this way completes entire iteration. Pre-Order is one of the special cases of depth first search order.

Breadth-first Search order

Breadth-first order, which always attempts to visit the same level sibling nodes first. This is also called a level-order traversal. This has to remember all same level nodes in a list to do this iteration. It prints all the nodes closes to root and gradually approaches to the leaf nodes.

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

delete single linked list, Stack, Tree and Binary tree, Binary tree, traverse Binary tree, Binary search tree, double Binary tree, mirror Binary tree, height of Binary tree,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan