Inorder Traversal

Inorder traversal visits the node in the order: Left -> Root -> Right

Algorithm for Inorder Traversal:

Inorder(tree)

Traverse the left subtree, i.e., call Inorder(left->subtree)
Visit the root.
Traverse the right subtree, i.e., call Inorder(right->subtree)

Uses of Inorder Traversal:

In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.
To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.
Inorder traversal can be used to evaluate arithmetic expressions stored in expression trees.

Code Snippet for Inorder Traversal:

C++

// Given a binary tree, print its nodes in inorder
void printInorder(struct Node* node)
{
    if (node == NULL)
        return;

    // First recur on left child
    printInorder(node->left);

    // Then print the data of node
    cout << node->data << " ";

    // Now recur on right child
    printInorder(node->right);
}

// Given a binary tree, print its nodes in inorder
void printInorder(struct node* node)
{
    if (node == NULL)
        return;

    // First recur on left child
    printInorder(node->left);

    // Then print the data of node
    printf("%d ", node->data);

    // Now recur on right child
    printInorder(node->right);
}

Java

void printInorder(Node node)
{
    if (node == null)
        return;

    // First recur on left child
    printInorder(node.left);

    // Then print the data of node
    System.out.print(node.key + " ");

    // Now recur on right child
    printInorder(node.right);
}

Python3

# A function to do inorder tree traversal
def printInorder(root):

    if root:

        # First recur on left child
        printInorder(root.left)

        # Then print the data of node
        print(root.val, end=" "),

        # Now recur on right child
        printInorder(root.right)

// Given a binary tree, print
// its nodes in inorder
void printInorder(Node node)
{
    if (node == null)
        return;

    // First recur on left child
    printInorder(node.left);

    // Then print the data of node
    Console.Write(node.key + " ");

    // Now recur on right child
    printInorder(node.right);
}

Javascript

// Given a binary tree, print its nodes in inorder
function printInorder(node) {
    if (node == null)
        return;

    // First recur on left child */
    printInorder(node.left);

    // Then print the data of node
    console.log(node.key + " ");

    // Now recur on right child
    printInorder(node.right);
}

Output

Inorder traversal of binary tree is 
4 2 5 1 3

Time Complexity: O(N)
Auxiliary Space: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. In this article, we will discuss about all the tree traversal techniques along with their uses.

Table of Content

Tree Traversal Meaning
Tree Traversal Techniques
Inorder Traversal
Preorder Traversal
Postorder Traversal
Level Order Traversal
Other Tree Traversals
Frequently Asked Questions (FAQs) on Tree Traversal Techniques

Inorder Traversal

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us