How to traverse a Binary tree?

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); 
  } 
}

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); 
  } 
}

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);
  } 
}

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.

About our authors: Team EQA

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

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions