// 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
Created
July 13, 2024 12:46
-
-
Save qqwqqw689/6c15f0ebf415c530f08f047766d49d85 to your computer and use it in GitHub Desktop.
Inorder Tree Traversal without Recursion
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment