How to perform an iterative inorder traversal of a binary tree

An iterative inorder traversal of a binary tree is done using the stack data structure.

Algorithm

  • Initialize an empty stack.

  • Push the current node (starting from the root node) onto the stack. Continue pushing nodes to the left of the current node until a NULL value is reached.

  • If the current node is NULL and the stack is not empty:

    1. Remove and print the last item from the stack.
    2. Set the current node to be the node to the right of the removed node.
    3. Repeat the second step of the algorithm.
  • If the current node is NULL ​and the stack is empty, then the algorithm has finished.

The algorithm is illustrated on a sample binary tree below:

1 of 19

Implementation

#include <iostream>
#include <stack>
using namespace std;
struct Node
{
int data;
struct Node* left;
struct Node* right;
Node (int data)
{
this->data = data;
left = right = NULL;
}
};
void inOrderTraversal(Node *root)
{
// Create an empty stack.
stack<Node*> stack;
// Start from the root node.
Node *curr = root;
// If the current node is null and stack is also empty, the algorithm terminates.
while (!stack.empty() || curr != NULL)
{
// Push the current node to the stack and set current=current->left.
if (curr != NULL)
{
stack.push(curr);
curr = curr->left;
}
else // If the curr node is NULL.
{
curr = stack.top();
stack.pop(); // Pop the node on top of stack.
cout << curr->data << " "; // Print it.
curr = curr->right;
}
}
}
// Driver code
int main() {
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);
inOrderTraversal(root);
return 0;
}
Copyright ©2024 Educative, Inc. All rights reserved