Inorder Traversal in Binary Tree

In Inorder traversal, first we have to visit the left subtree ,then visit the root and then right subtree.

Process is defined as follows :

• process the left subtree
• Visit the root node.
• process the right subtree.

Working Process of Inorder Traversal

Code Implementation of Inorder Traversal

Inorder traversing can be implement in two ways :
1- Recursive Implementation
2- Non-Recursive Implementation.

• Debug the recursive and Non-recursive code with the below Binary tree :

Recursive Implementation of InOrder Traversal

#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
struct BinaryTreeNode                  // Node Structure Initialization
{
	char  data;                         // for data element
	struct BinaryTreeNode* left;   // for storing the address of left child
	struct BinaryTreeNode* right;  // for storing the address of right child
};
// Inorder Traversing method.
void InOrderTraversing(struct BinaryTreeNode* rootNode)
{
	if (rootNode)
	{
		InOrderTraversing(rootNode->left);
		std::cout << rootNode->data << " ";
		InOrderTraversing(rootNode->right);
	}
}
int main()
{
	//initialize 5 node to create the binary tree.
	struct BinaryTreeNode* A = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* B = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* C = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* D = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* E = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	//address arrangement.
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	//leaf node has zero child.
	C->left = NULL;
	C->right = NULL;
	D->left = NULL;
	D->right = NULL;
	E->left = NULL;
	E->right = NULL;
	//Data Initilization.
	A->data = 'A';
	B->data = 'B';
	C->data = 'C';
	D->data = 'D';
	E->data = 'E';
	// call the function to print the Inorder Sequence
	printf("InOrder Traversal will be : ");
	InOrderTraversing(A);
	_getch();
	return 0;
}

Non-Recursive Implementation of InOrder Traversal

#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<stack>
struct BinaryTreeNode                  // Node Structure Initialization
{
	char  data;                         // for data element
	struct BinaryTreeNode* left;   //for storing the address of left child
	struct BinaryTreeNode* right;  // for storing the address of right child
};
// InOrder Traversing method.
void InOrderTraversing(struct BinaryTreeNode* rootNode)
{
	//For Stack ,we used stack library of STL.
	std::stack <struct BinaryTreeNode*> StackForRoot;
	while (true)
	{
		while (rootNode)
		{
			//store the rootNode of all subtree into the stack.
			StackForRoot.push(rootNode);
			rootNode = rootNode->left;
		}
		//When no node is availabe in Left then pop the stack
		if (!StackForRoot.empty())
		{
			//Store the top value of stack.
			rootNode = StackForRoot.top();
			//Pop the top value.
			StackForRoot.pop();
			//print the node Data.
			std::cout << rootNode->data << " ";
			rootNode = rootNode->right;
		}
		else
			break;
	}
}
int main()
{
	//initialize 5 node to create the binary tree.
	struct BinaryTreeNode* A = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* B = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* C = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* D = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* E = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	//address arrangement.
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	//leaf node has zero child.
	C->left = NULL;
	C->right = NULL;
	D->left = NULL;
	D->right = NULL;
	E->left = NULL;
	E->right = NULL;
	//Data Initilization.
	A->data = 'A';
	B->data = 'B';
	C->data = 'C';
	D->data = 'D';
	E->data = 'E';
	// call the function to print the Preorder Sequence
	printf("InOrder Traversal will be : ");
	InOrderTraversing(A);
	_getch();
	return 0;
}

 Time & Space Complexity of InOrder Traversal

• For Recursive Implementation : Time Complexity will be O(n),
  and Space Complexity will be O(n).
• For Non-Recursive Implementation : Time Complexity will be O(n),and Space Complexity will be O(n).