Inorder Tree Traversal without Recursion

file.md

// C++ program to print inorder traversal
// using stack.

#include <bits/stdc++.h>
using namespace std;

// A binary tree Node has data, pointer to left child
// and a pointer to right child
struct Node {
	int data;
	struct Node* left;
	struct Node* right;
	Node(int data)
	{
		this->data = data;
		left = right = NULL;
	}
};

//Iterative function for inorder tree traversal
void inOrder(struct Node* root)
{
	stack<Node*> s;
	Node* curr = root;

	while (curr != NULL || s.empty() == false) {
		
		// Reach the left most Node of the
		// curr Node
		while (curr != NULL) {
			
			// Place pointer to a tree node on
			// the stack before traversing
			// the node's left subtree
			s.push(curr);
			curr = curr->left;
		}

		// Current must be NULL at this point
		curr = s.top();
		s.pop();

		cout << curr->data << " ";

		// we have visited the node and its
		// left subtree. Now, it's right
		// subtree's turn
		curr = curr->right;

	}
}

// Driver program to test above functions
int main()
{
	/* Constructed binary tree is
			1
			/ \
		2	 3
		/ \
	4	 5
	*/
	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);

	inOrder(root);
	return 0;
}

```cpp
// C++ program for Inorder Morris Traversal
#include <bits/stdc++.h>
using namespace std;

// A binary tree tNode has data, a pointer to left child
// and a pointer to right child
struct tNode {
	int data;
	struct tNode* left;
	struct tNode* right;
};

// Function to traverse the binary tree 
// without recursion and without stack
void inOrder(struct tNode* root)
{
	struct tNode *current, *pre;

	if (root == NULL)
		return;

	current = root;
	while (current != NULL) {

		if (current->left == NULL) {
			cout << current->data << " ";
			current = current->right;
		}
		else {

			// Find the inorder predecessor of current
			pre = current->left;
			while (pre->right != NULL
				&& pre->right != current)
				pre = pre->right;

			// Make current as the right child of its
			// inorder predecessor 
			if (pre->right == NULL) {
				pre->right = current;
				current = current->left;
			}

			// Revert the changes made in the 'if' part to
			// restore the original tree i.e., fix the right
			// child of predecessor
			else {
				pre->right = NULL;
				cout << current->data << " ";
				current = current->right;
			}
		}
	}
}

struct tNode* newtNode(int data)
{
	struct tNode* node = new tNode;
	node->data = data;
	node->left = NULL;
	node->right = NULL;

	return (node);
}

// Driver code
int main()
{
	struct tNode* root = newtNode(1);
	root->left = newtNode(2);
	root->right = newtNode(3);
	root->left->left = newtNode(4);
	root->left->right = newtNode(5);

	inOrder(root);

	return 0;
}
// This code is contributed by Raunak Singh

```cpp