Inorder Traversal of Binary Tree

Inorder Traversal is a method to traverse a tree such that for each node, you first traverse its left subtree, then visit the node itself, and finally traverse its right subtree.

Examples:

Input:

Output: [2, 1, 3]
Explanation: The Inorder Traversal visits the nodes in the following order: Left, Root, Right. Therefore, we visit the left node 2, then the root node 1 and lastly the right node 3.

Input :

Output: [4, 2, 5, 1, 3, 6]
Explanation: Inorder Traversal (Left -> Root -> Right). Visit 4 -> 2 -> 5 -> 1 -> 3 -> 6, resulting in 4 2 5 1 3 6.

How does Inorder Traversal work?

[Approach] Using Recursion

The main idea is to traverse the tree recursively, starting from the root node, first completely traverse the left subtree, then visit the root node itself, and finally completely traverse the right subtree.

#include<iostream>
#include <vector>
using namespace std;

//Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = right = NULL;
    }
};

void inOrder(Node* node, vector<int>& res) {
    if (node == nullptr)
        return;
        
    // Traverse the left subtree first
    inOrder(node->left, res);
    
    // Visit the current node
    res.push_back(node->data);
    
    // Traverse the right subtree last
    inOrder(node->right, res);
}

int main() {
    // Create binary tree
    //       1
    //      /  \
    //    2     3
    //   / \     \
    //  4   5     6
    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);

    vector<int> res;
    inOrder(root, res);
    
    for( int node : res) 
        cout << node << " ";

    return 0;
}

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

//Node Structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int x) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inOrder(struct Node* node) {
    if (node == NULL)
        return;
        
    // Traverse the left subtree first
    inOrder(node->left);
    
    // Visit the current node
    printf("%d ", node->data);
    
    // Traverse the right subtree last
    inOrder(node->right);
}

int main() {
    // Create binary tree
    //       1
    //      /  \
    //    2     3
    //   / \     \
    //  4   5     6
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);

    inOrder(root);
    printf("\n");

    return 0;
}

import java.util.ArrayList;

//Node Structure
class Node {
    int data;
    Node left;
    Node right;

    Node(int x) {
        data = x;
        left = right = null;
    }
}

public class GFG {

    static void inOrder(Node node, ArrayList<Integer> res) {
        if (node == null)
            return;
        
        // Traverse the left subtree first
        inOrder(node.left, res);
        
        // Visit the current node
        res.add(node.data);
        
        // Traverse the right subtree last
        inOrder(node.right, res);
    }

    public static void main(String[] args) {
        // Create binary tree
        //       1
        //      /  \
        //    2     3
        //   / \     \
        //  4   5     6
        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);

        ArrayList<Integer> res = new ArrayList<>();
        inOrder(root, res);

        for(int node : res)
            System.out.print(node + " ");
    }
}

#Node Structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

def inOrder(node, res):
    if node is None:
        return

    # Traverse the left subtree first
    inOrder(node.left, res)

    # Visit the current node
    res.append(node.data)

    # Traverse the right subtree last
    inOrder(node.right, res)

if __name__ == "__main__":
    # Create binary tree
    #       1
    #      /  \
    #    2     3
    #   / \     \
    #  4   5     6
    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)

    res = []
    inOrder(root, res)

    for node in res:
        print(node, end=" ")

using System;
using System.Collections.Generic;

//Node Structure
class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GFG {

    static void inOrder(Node node, List<int> res) {
        if (node == null)
            return;

        // Traverse the left subtree first
        inOrder(node.left, res);

        // Visit the current node
        res.Add(node.data);

        // Traverse the right subtree last
        inOrder(node.right, res);
    }

    static void Main(string[] args) {
        // Create binary tree
        //       1
        //      /  \
        //    2     3
        //   / \     \
        //  4   5     6
        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);

        List<int> res = new List<int>();
        inOrder(root, res);

        foreach(int node in res)
            Console.Write(node + " ");
    }
}

//Node Structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

function inOrder(node, res) {
    if (node === null)
        return;

    // Traverse the left subtree first
    inOrder(node.left, res);

    // Visit the current node
    res.push(node.data);

    // Traverse the right subtree last
    inOrder(node.right, res);
}

//Driver Code
// Create binary tree
//       1
//      /  \
//    2     3
//   / \     \
//  4   5     6
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);

const res = [];
inOrder(root, res);

console.log(res.join(' '));

4 2 5 1 3 6 

Time Complexity: O(n)
Auxiliary Space: O(h), 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 log n (when the tree is a complete tree)

Key Properties:

• If applied to a Binary Search Tree (BST), it returns elements in sorted order.
• Ensures that nodes are processed in a hierarchical sequence, making it useful for expression trees and BSTs.

Related Articles:

• Types of Tree Traversals
• Iterative inorder traversal
• Construct binary tree from preorder and inorder traversal
• Morris traversal for inorder traversal of tree
• Inorder traversal without recursion