Inorder Traversal

A Depth-First Search Technique for Visiting Left, Root, Right in Trees

Introduction

Inorder Traversal visits the left subtree first, then the root, and finally the right subtree. It’s widely used in binary search trees (BST) to visit nodes in sorted order.

Inorder Traversal visits the node in the order: left->root->right

How Inorder Traversal Works?

1

Traverse Left Subtree

  • The left subtree is visited first, following the same method (left → root → right).
2

Visit Root

  • After the left subtree, the root node is visited.
3

Traverse Right Subtree

  • Finally, the right subtree is recursively traversed in the same order (left → root → right).

Implementation of Inorder Traversal

//inorder.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
    this->data = data;
    this->left = NULL;
    this->right = NULL;
}
};
Node *buildTree(Node *root)
{
cout << "Enter The data: " << endl;
int data;
cin >> data;
root = new Node(data);
if (data == -1)
{
    return NULL;
}
cout << "Enter data for left : " << endl;
root->left = buildTree(root->left);
cout << "Enter data for right: " << endl;
root->right = buildTree(root->right);
return root;
}
void inorder(Node *root)
{
if (!root)
    return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
int main()
{
// creating tree
Node *root = NULL;
root = buildTree(root);

// inorder order
inorder(root);
}

Time Complexity

Time Complexity: O(n)

  • The function visits each node in the tree exactly once. Given that there are n nodes, the function performs n operations, resulting in O(n) time complexity.

Space Complexity

Space Complexity:O(h),where h is the height of the tree.