Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

iterative
inorder
traversal

How to perform an iterative inorder traversal of a binary tree

Educative Answers Team

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;
}

RELATED TAGS

iterative
inorder
traversal
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring