inorder(root)
a. Traverse the left subtree (inorder(root->left))
b. visit the root
c. Traverse the right subtree (inorder(root->right))
2. by non recursive method
This method is implemented by the use of stack.
a. create an empty stack
b. initialize current node as root node.
c. push current into the stack while current->left != NULL
update current as current=current->left
d. repeat while current is NULL and stack is not empty
1. pop the element from the stack and update
current equal to the popped element
2. print info of current
3.update current=current->right
C++ code to implement in-order traversal
#include<iostream>
#include<stack>
using namespace std;
/*structure to store a BST*/
struct node
{
int info;
node *left,*right;
};
/*Method to create a newNode if a tree does not exist*/
node *newNode(int n)
{
node *ptr=new node;
ptr->info=n;
ptr->left=ptr->right=NULL;
return ptr;
}
/*Method to insert given node in the BST */
node *insert(node* node,int info)
{
if(node==NULL)
{
return newNode(info);
}
if(info < node->info)
{
node->left=insert(node->left,info);
}
else
{
node->right=insert(node->right,info);
}
return node;
}
/*Method to print inorder traversal of a BST*/
void inorder(node *root)
{
stack<node*> stack;
node *curr=root;
while(!stack.empty() || curr!=NULL)
{
/*If current node is not NULL push the node in stack*/
if(curr!=NULL)
{
stack.push(curr);
curr=curr->left;
}
/*If current node is empty or NULL pop it from the stack */
else
{
curr=stack.top();
stack.pop();
cout<<curr->info<<" ";
curr=curr->right;
}
}
}
//main program
int main()
{
node* root=newNode(60);
insert(root,50);
insert(root,70);
insert(root,40);
insert(root,30);
insert(root,80);
insert(root,75);
insert(root,65);
insert(root,45);
insert(root,55);
insert(root,90);
insert(root,67);
cout<<"Inorder traversal :";
/*Call/invoke statement for inorder method*/
inorder(root);
cout<<endl;
return 0;
}
Algorithm:
2. by non recursive method
This method is implemented by the use of stack.
C++ code to implement in-order traversal
Output