Inorder Traversal in a Binary Tree

Inorder traversal in a binary tree defines that the root node of a tree/ subtree is visited after its left child node and before its right child node. It can be defined as Left-Root-Right. The Inorder Traversal process in Binary Trees can be done by recursive and non recursive methods.

Recursive Traversal

In recursive Inorder traversal the address of current node is stored in a pointer CURR. CURR pointer is initialized to the Root of the binary tree.

In all the subsequent recursive calls the CURR->LEFT or CURR->RIGHT nodes are passed as the last argument in the function. The node passed as last argument becomes the root for the subtree that is currently being traversed.

The traversal procedure is repeatedly called for left and right child nodes till CURR (pointer storing address of current node) becomes NULL.

Algorithm REC_TRAVERSAL(DATA, LEFT, RIGHT, ROOT)
1.	[ Initialize Pointer]  CURR=ROOT
2.	IF CURR <>NULL
    a.	REC_TRAVERSAL (DATA, LEFT, RIGHT, CURR->LEFT)
    b.	Process node CURR
    c.	REC_TRAVERSAL (DATA, LEFT, RIGHT, CURR->RIGHT)
3.	Exit

Non-Recursive Traversal

In non-recursive Inorder Traversal an intermediary storage data structure Stack is used to maintain the nodes of the leftmost branch of the Binary Tree. The left most branch is the series of nodes starting from root, following all the left child nodes ending in the left most leaf node.

Traversal begins from the root node. The current node is pushed onto the stack and its left child node becomes the current node. When the leaf node is pushed on the stack and CURR pointer gets updated with NULL from left pointer of leaf node, backtracking is done staring from leaf node. The last node pushed in the stacks is popped and stored in CURR pointer.

The node identified by CURR pointer is processed and checked for presence of Right child. If it exists, it is treated as a subtree that needs to be traversed in the same way we started from the root of the binary tree.

Algorithm NONREC_TRAVERSAL (DATA, LEFT, RIGHT, ROOT)
1.	[Initialize variables and stack] TOS=1, STK[TOP]=# , CURR=ROOT
2.	[Save the nodes of leftmost bracnch in the stack]
     Repeat steps 3 and 4 while CURR<> NULL
3.	 [Push  current node store in the stack]
     TOS=TOS+1
     STK[TOS]=CURR
4.	[update CURR pointer with Left Child node]
     CURR= CURR->LEFT
5.	[Pop last pushed leaf node and store in CURR pointer]
     CURR =STK[TOS],  TOS=TOS-1
6.	[Backtrack and process nodes while checking for a right child node]
    Repeat steps 7, 8 and 9 while CURR<> NULL
7.	[Process node]
    Process node CURR->DATA
8.	[Right child of CURR exists?]
    If CURR->RIGHT<> NULL
	CURR= CURR->RIGHT and go to step 2
9.	[Pop next node from stack]
    CURR=STK[TOS] ,    TOS=TOS-1
10.	END

Application of Inorder Traversal

One useful application of Inorder Traversal is printing all the nodes of the Binary Search Tree in ascending order of their node values. It is also used in finding the successor of a node with two child nodes which has to be deleted from a binary search tree.

Consider the following Binary Search Tree-