Program to implement Inorder Traversal of Binary Tree

How does Inorder Traversal of Binary Tree work?

Below is the code implementation of the inorder traversal:

C++

// C++ program for inorder traversals
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
    Node(int v)
    {
        data = v;
        left = right = NULL;
    }
};
 
// Function to print inorder traversal
void printInorder(struct Node* node)
{
    if (node == NULL)
        return;
 
    // First recur on left subtree
    printInorder(node->left);
 
    // Now deal with the node
    cout << node->data << " ";
 
    // Then recur on right subtree
    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);
    root->right->right = new Node(6);
 
    // Function call
    cout << "Inorder traversal of binary tree is: \n";
    printInorder(root);
 
    return 0;
}

Java

// Java program for inorder traversals
import java.util.*;
 
// Structure of a Binary Tree Node
class Node {
    int data;
    Node left, right;
 
    Node(int v)
    {
        data = v;
        left = right = null;
    }
}
 
// Main class
class GFG {
 
    // Function to print inorder traversal
    public static void printInorder(Node node)
    {
        if (node == null)
            return;
 
        // First recur on left subtree
        printInorder(node.left);
 
        // Now deal with the node
        System.out.print(node.data + " ");
 
        // Then recur on right subtree
        printInorder(node.right);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        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);
        root.right.right = new Node(6);
 
        // Function call
        System.out.println(
            "Inorder traversal of binary tree is: ");
        printInorder(root);
    }
}
// This code is contributed by prasad264

Python3

# Structure of a Binary Tree Node
class Node:
    def __init__(self, v):
        self.data = v
        self.left = None
        self.right = None
 
# Function to print inorder traversal
def printInorder(node):
    if node is None:
        return
 
    # First recur on left subtree
    printInorder(node.left)
 
    # Now deal with the node
    print(node.data, end=' ')
 
    # Then recur on right subtree
    printInorder(node.right)
 
# Driver code
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(6)
 
    # Function call
    print("Inorder traversal of binary tree is:")
    printInorder(root)

C#

// C# program for inorder traversals
 
using System;
 
// Structure of a Binary Tree Node
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int v)
    {
        data = v;
        left = right = null;
    }
}
 
// Class to store and print inorder traversal
public class BinaryTree {
    // Function to print inorder traversal
    public static void printInorder(Node node)
    {
        if (node == null)
            return;
 
        // First recur on left subtree
        printInorder(node.left);
 
        // Now deal with the node
        Console.Write(node.data + " ");
 
        // Then recur on right subtree
        printInorder(node.right);
    }
 
    // Driver code
    public static void Main()
    {
        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);
        root.right.right = new Node(6);
 
        // Function call
        Console.WriteLine(
            "Inorder traversal of binary tree is: ");
        printInorder(root);
    }
}

Javascript

// JavaScript program for inorder traversals
 
// Structure of a Binary Tree Node
class Node {
    constructor(v) {
        this.data = v;
        this.left = null;
        this.right = null;
    }
}
 
// Function to print inorder traversal
function printInorder(node) {
    if (node === null) {
        return;
    }
     
    // First recur on left subtree
    printInorder(node.left);
     
    // Now deal with the node
    console.log(node.data);
     
    // Then recur on right subtree
    printInorder(node.right);
}
 
// Driver code
const 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);
root.right.right = new Node(6);
 
// Function call
console.log("Inorder traversal of binary tree is: ");
printInorder(root);

Output

Inorder traversal of binary tree is: 
4 2 5 1 3 6

Explanation:

How inorder traversal works

Complexity Analysis:

Time Complexity: O(N) where N is the total number of nodes. Because it traverses all the nodes at least once.
Auxiliary Space: O(1) if no recursion stack space is considered. Otherwise, O(h) where h is the height of the tree

In the worst case, h can be the same as N (when the tree is a skewed tree)
In the best case, h can be the same as logN (when the tree is a complete tree)

Use cases of Inorder Traversal:

In the case of BST (Binary Search Tree), if any time there is a need to get the nodes in non-decreasing order, the best way is to implement an inorder traversal.

Related Articles:

Inorder Traversal of Binary Tree

Inorder traversal is defined as a type of tree traversal technique which follows the Left-Root-Right pattern, such that:

The left subtree is traversed first

Then the root node for that subtree is traversed

Finally, the right subtree is traversed

Inorder traversal

Tags:

#Binary Tree #Inorder Traversal #DSA #Tree #Tree