Tree traversal - inorder, preorder, and postorder (the three main traversals)

Алгоритм, Tree, Дерево

Tree traversal means visiting every node in the tree. For example, you can add all values to the tree or find the largest one. For all these operations, you will need to visit each node of the tree.

Linear data structures such as arrays, stacks, queues, and linked lists have only one way to read data. But a hierarchical data structure like a tree can be traversed in many different ways.

Let's think about how we can read the elements of the tree in the image shown above.

Starting from the top, left to right

1 -> 12 -> 9 -> 5 -> 6

Starting from the bottom, left to right

5 -> 6 -> 12 -> 9 -> 1

Although this process is somewhat simple, it does not take into account the hierarchy of the tree, only the depth of the nodes.

Instead, we use traversal methods that respect the underlying structure of the tree, i.e.

struct node {
    int data;
    struct node* left;
    struct node* right;
}

The struct node pointed to by left (left) and right (right) may have other left and right children, so we must treat them as subtrees, not subnodes.

According to this structure, each tree is a combination

• Node carrying data
• Two subtrees

Remember that our goal is to visit every node, so we need to visit all nodes in the subtree, visit the root node, and also visit all the nodes in the right subtree.

Depending on the order in which we do it, there can be three types of traversal .

Centered traversal type (Inorder traversal)

1. First visit all nodes in the left subtree
2. Then the root node
3. Visit all nodes in the right subtree

inorder(root->left)
display(root->data)
inorder(root->right)

Direct traversal type (Preorder traversal)

1. Visit the root node
2. Visit all nodes in the left subtree
3. Visit all nodes in the right subtree

display(root->data)
preorder(root->left)
preorder(root->right)

Postorder traversal

1. visit all nodes in the left subtree
2. visit the root node
3. visit all nodes in the right subtree

postorder(root->left)
postorder(root->right)
display(root->data)

Let's visualize the centered traversal type. Let's start with the root node.

First we traverse the left subtree. We also need to remember to visit the root node and the right subtree when the tree is ready.

Let's put it all on a stack so we remember.

Now let's move on to the subtree specified at the top of the stack.

Again, we follow the same rule of centered type (inorder)

Left subtree -> root -> right subtree

After traversing the left subtree, we are left with

Since node "5" has no subtrees, we print it directly. After that, we print its parent node "12" and then its right child "6".

Putting everything on the stack was useful, because now that the left subtree of the root node has been traversed, we can print it out and move on to the right subtree.

After going through all the elements, the centered traversal type (inorder traversal) looks like this:

5 -> 12 -> 6 -> 1 -> 9

We don't need to create the stack ourselves because recursion maintains the correct order for us.

The complete code for centered (inorder), direct (preorder) and reverse (postorder) traversal type in the C programming language is below:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node* left;
    struct node* right;
};

void inorder(struct node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ->", root->data);
    inorder(root->right);
}

void preorder(struct node* root){
    if(root == NULL) return;
    printf("%d ->", root->data);
    preorder(root->left);
    preorder(root->right);
}

void postorder(struct node* root) {
    if(root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ->", root->data);
}


struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct node* insertLeft(struct node *root, int value) {
    root->left = createNode(value);
    return root->left;
} 


struct node* insertRight(struct node *root, int value){
    root->right = createNode(value);
    return root->right;
}


int main(){
    struct node* root = createNode(1);
    insertLeft(root, 12);
    insertRight(root, 9);

    insertLeft(root->left, 5);
    insertRight(root->left, 6);

    printf("Inorder traversal \n");
    inorder(root);

    printf("\nPreorder traversal \n");
    preorder(root);

    printf("\nPostorder traversal \n");
    postorder(root);
}

The output of the code will look like this:

Inorder traversal                                                                                                                                                         
5 ->12 ->6 ->1 ->9 ->                                                                                                                                                     
Preorder traversal                                                                                                                                                        
1 ->12 ->5 ->6 ->9 ->                                                                                                                                                     
Postorder traversal                                                                                                                                                       
5 ->6 ->12 ->9 ->1 ->