Inorder Traversal (Practice)

Follow the below steps to solve the problem:

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

Below is the implementation of the above algorithm:

C++

// C++ program for different tree traversals
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
/* 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);
}
 
/* Driver code*/
int main()
{
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
 
    cout << "\nInorder traversal of binary tree is \n";
    printInorder(root);
 
    return 0;
}

C

// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
/* 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);
}
 
/* Driver code*/
int main()
{
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    printf("\nInorder traversal of binary tree is \n");
    printInorder(root);
 
    getchar();
    return 0;
}

Java

// Java program for different tree traversals
 
/* Class containing left and right child of current
   node and key value*/
class Node {
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
 
class BinaryTree {
    // Root of Binary Tree
    Node root;
 
    BinaryTree() { root = null; }
 
    /* 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 */
        System.out.print(node.key + " ");
 
        /* now recur on right child */
        printInorder(node.right);
    }
 
    // Wrappers over above recursive functions
    void printInorder() { printInorder(root); }
 
    // Driver code
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        System.out.println(
            "\nInorder traversal of binary tree is ");
        tree.printInorder();
    }
}

Python

# Python3 program to for tree traversals
 
# A class that represents an individual node in a
# Binary Tree
 
 
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
 
 
# 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),
 
        # now recur on right child
        printInorder(root.right)
 
 
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
 
print "\nInorder traversal of binary tree is"
printInorder(root)

C#

// C# program for different tree traversals
using System;
 
/* Class containing left and right child of current
node and key value*/
class Node {
    public int key;
    public Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    // Root of Binary Tree
    Node root;
 
    BinaryTree() { root = null; }
 
    /* 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);
    }
 
    // Wrappers over above recursive functions
    void printInorder() { printInorder(root); }
 
    // Driver code
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        Console.WriteLine(
            "\nInorder traversal of binary tree is ");
        tree.printInorder();
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// javascript program for different tree traversals
 
/* Class containing left and right child of current
   node and key value*/
class Node {
    constructor(val) {
        this.key = val;
        this.left = null;
        this.right = null;
    }
}
     
 
    /* 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 */
        document.write(node.key + " ");
 
        /* now recur on right child */
        printInorder(node.right);
    }
 
    // Driver method
 
        var root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
 
        document.write("<br/>Inorder traversal of binary tree is <br/>");
        printInorder(root);
 
// This code is contributed by umadevi9616
</script>

Output

Inorder traversal of binary tree is 
4 2 5 1 3

Time Complexity: O(N)
Auxiliary Space: O(log N)

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

C++

C

Java

Python

C#

Javascript

Uses of Inorder traversal:

DFS traversal of a Tree

Categories

Contact US

Inorder Traversal (Practice)

C++

C

Java

Python

C#

Javascript

Uses of Inorder traversal:

DFS traversal of a Tree

Similar Reads

Categories

Contact US