In order Traversal

Introduction

In-order 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.

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

How In-order Traversal Works?

Traverse Left Subtree

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

Visit Root

After the left subtree, the root node is visited.

Traverse Right Subtree

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

Visualization of In-order Traversal

Implementation of In-order Traversal

//in-order.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);

// in-order order
inOrder(root);
}

print("We're Working")

console.log("We're Working");

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.

In order Traversal

On this page