The following is the non-recursive algorithm to perform in-order tree traversal on a binary search tree. The following algorithm uses a stack as an auxiliary data structure in order to accomplish the in-order transversal.

INORDER-TREE-TRAVERSE (T)

//initialize an empty Stack

1. A= Empty Stack;

//put the root of tree into current node variable.

2. Crnt_node =T.root

// while loop is used to check the value of current node.

3. While Crnt_node != NIL or Stack-Empty (A)= FALSE

//if the current node value is not null

4. if Crnt_node != NIL then

//insert the value of current node into stack A

5. PUSH (A, Crnt_node);

// store the left child of tree into current node

6. Crnt_node=Crnt_node. left

7. else

// retrieve the element from stack and store it into current node.

Crnt_node =POP (A)

//display the current value

8. Display (Crnt_node)

//store the right child of tree into current node.

9. Crnt_node = Crnt_node. right

Explanation of Algorithm:

• The algorithm starts from the Crnt_node, which contains the root node initially.

• In line 3, while loop is used to traverse the left nodes (left children) from the root.

• In line 4-6, Crnt_node is pushed into stack if the Crnt_node is not NIL.

• In line 7-9, if Crnt_node is NIL , Crnt_node is displayed and starts traversing right children by updating Crnt_node with its right child.

• While loop exits when the Crnt_node is NIL and the stack is empty.

Since the above algorithm traversing all the nodes in the binary search tree, if n is the number of nodes in the binary search tree, the above algorithm takes time to traverse.

The following is the non-recursive algorithm to perform in-order tree traversal on a binary search tree without using stack as an auxiliary data structure, but using a pointer called previous(Prev). Previous pointer is used to compare with current node.

INORDER-TREE-TRAVERSE (T)

//put the root of tree into current node variable.

1. Crnt_node=T.root

// while loop is used to check the value of current node.

2. While crnt_node != NIL

//if the current node value is not null

3. if crnt_node.left = NIL

//display the current value

4. Display (Crnt_node)

//add the right child of tree into current node variable

5. Crnt_node = Crnt_node. right

6. else

//add the left child of current node into previous node variable.

7. Prvs_node = Crnt_node. left

//while loop is used to check the value of previous node and compare previous

//node with current node

8. While Prvs_node != NIL and Prvs_node.right != Crnt_node

//add right child of previous node into previous node variable

9. Prvs_node =Prvs_node.right

//check the value of right child of previous node.

10. if Prvs_node.right = NIL

//store the current node value into previous node

11. Prvs_node.right =Crnt_node

12. Crnt_node = Crnt_node.left

13. else

//put null into right child of previous node

14. Prvs_node.right = NIL

15. Display (Crnt_node)

//store the right child of tree into current node.

16. Crnt_node = Crnt_node. right

Explanation of Algorithm:

• In line 1, algorithm initializes current node with root.

• in line 2, “While” loop runs until the Crnt_node is NIL.

• In line 3 -7, if left child of current node is NIL, then the Crnt_node is displayed and updates the Crnt_node with the right child of the current node. Otherwise updates the Prvs_node with the left child of current node.

• in line 8, “While” loop is used to find the previous node(or predecessor) to Crnt_node.

• In line 10-12, if the right child of previous node is NIL, then assign current node as right child of previous node and assign left child of the current node to Crnt_node variable.

• In line 13-16, the tree is restored to original .

The above algorithm also takes time to traverse the binary search tree with n nodes.