Tree Traversals: Preorder, Postorder, Inorder

Tree traversals are used to traverse trees of different shapes. Traversal of a data structure means accessing the entire data stored in the data structure to perform some task. Most linear data structures like Arrays, Linked Lists, Queues, and Stacks have only a few logical ways of traversal but this is not true for trees.

Then, what really are trees? A tree is a non-linear hierarchical data structure that contains nodes connected via edges.

Types of Tree Traversals

There are multiple ways of tree traversal due to its non-linear structure. Some typical tree traversal algorithms are

  1. Preorder Traversal
  2. Postorder Traversal
  3. Inorder Traversal

First Let’s create a binary tree and then elaborate on preorder, postorder and inorder traversals.

Explanation: Binary Tree Implementation to test Tree Traversals

Suppose that we have the following binary tree implemented

struct BST {
          int data;
          BST* left, * right;
public:
// Default constructor.
          BST() {
                    data = 0;
                    left = NULL;
                    right = NULL;
          }
          // Parameterized constructor.
          BST(int value){
                    data = value;
                    left = right = NULL;
          }
          // Insert function.
          BST* Insert(BST* root, int value){
                    if (!root) {
                              // Insert the first node, if the root is NULL.
                              return new BST(value);
                    }
                    // Insert data.
                    if (value > root->data) {
                              // Insert right node data, if the 'value'
                              // to be inserted is greater than the 'root' node data.
                              // Process right nodes.
                              root->right = Insert(root->right, value);
                    }
                    else if (value < root->data) {
                              // Insert left node data, if the 'value'
                              // to be inserted is smaller than the 'root' node data.
                              // Process left nodes.
                              root->left = Insert(root->left, value);
                    }
                    // Return 'root' node, after insertion.
                    return root;
          }
};
// driver function
int main(){
          BST tree, * tree_root = NULL;
          tree_root = tree.Insert(tree_root, 50);
          tree.Insert(tree_root, 30);
          tree.Insert(tree_root, 20);
          tree.Insert(tree_root, 40);
          tree.Insert(tree_root, 70);
          tree.Insert(tree_root, 60);
          tree.Insert(tree_root, 80);
          return 0;
}

The tree created can be visualized as

Tree Traversals
Binary Tree For Traversals: Preorder, Postorder, Inorder

1. Preorder Traversal

Pre-order traversal is used to get the prefix expression of a tree.

Algorithm Approach:

  1. Visit the root node
  2. Traverse the left subtree
  3. Traverse the right subtree
void Preorder(BST* root)
{
          if (!root) {
                    return;
          }
          cout << root->data << " ";
          Preorder(root->left);
          Preorder(root->right);
}

Output

The pre-order traversal of the above tree is 50, 30, 20, 40, 70, 60, 80.

2. Postorder Traversal

Post-order traversal is used to get the postfix expression of the given tree.

Algorithm Approach:

  1. Traverse the left subtree
  2. Traverse the right subtree
  3. Visit the root node
void Postorder(BST* root)
{
          if (!root) {
                    return;
          }
          Postorder(root->left);
          Postorder(root->right);
          cout << root->data << " ";
}

3. Inorder Traversal

In order, traversal gives the nodes of the tree in increasing order. To get nodes in decreasing order, traverse the right subtree, visit the root node, and then traverse the left subtree.

Algorithm Approach:

  1. Traverse the left subtree
  2. Visit the root node
  3. Traverse the right subtree
void Inorder(BST* root)
{
          if (!root) {
                    return;
          }
          Inorder(root->left);
          cout << root->data << " ";
          Inorder(root->right);
}

Output:

The in-order traversal of the above tree is 20, 30, 40, 50, 60, 70, 80.

Stay in the Loop

Get the daily email from Algoideas that makes reading the news actually enjoyable. Join our mailing list to stay in the loop to stay informed, for free.

Latest stories

- Advertisement -

You might also like...