Tree Traversals

A binary tree is traversed when one needs to access or display its elements. Each method produces a different order of elements that may be useful in scenarios when needed. There are 3 methods for traversing a binary tree:

Inorder [Left – Root – Right]

In this traversal, the left child node is visited first, it’s root node is visited next and then the right child node. This is repeated recursively until all the elements of the tree are traversed.

Algorithmically, we can write the steps as:

1. Traverse the left subtree, recursively call inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, recursively call inorder(right-subtree)

Code for Inorder Traversal

void inorder(struct Node* node) 
{
    if (node == NULL) 
        return;
  
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}

Applications

Inorder traversal can be used to find the nodes in the non-decreasing order in a binary search tree.

Preorder [Root – Left – Right]

In this traversal, the root node is visited first, then its left child and later its right child. This is repeated recursively until all the elements of the tree are traversed.

Algorithmically, we can write the steps as:

1. Visit the root.
2. Traverse the left subtree, recursively call preorder(left-subtree)
3. Traverse the right subtree, recursively call preorder(right-subtree).

Code for Preorder Traversal

void preorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
  
    cout << node->data << " "; 
    preorder(node->left);  
    preorder(node->right); 
}  

Applications

1. Preorder traversal can be used to create a copy of the tree.
2. It can be used to evaluate Prefix expressions.

Postorder [Left – Right – Root]

In this traversal, the left child node is visited first, then its right child and then its root node. This is repeated recursively until all the elements of the tree are traversed.

Algorithmically, we can write the steps as:

1. Traverse the left subtree, recursively call postorder(left-subtree)
2. Traverse the right subtree, recursively call postorder(right-subtree)
3. Visit the root.

Code for Postorder Traversal

void postorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
  
    postorder(node->left); 
    postorder(node->right); 
    cout << node->data << " "; 
} 

Applications

Postorder traversal can be used to delete a tree.

Time Complexity

The time complexity for every tree traversal is O(n). The time taken increases linearly with the elements of the tree.

Videos

• Tree Traversal Techniques | mycodeschool Explanation video of the traversal techniques.
• Binary tree traversal: Preorder, Inorder, Postorder | mycodeschool