Nonrecursive Algorithm to Inorder Traverse Binary Tree

In previous post, I discussed the nonrecursive algorithm with stack to inorder traverse a binary tree. That's also pretty straightforward. In fact, we can implement the inorder traversal of binary trees without stack. This is more complicated but elegant.

For this approach, I use one more pointer to record the subtree already visited. Also, we need keep in mind that we are doing INORDER traversal. Therefore, if the right subtree of a node has been visited, the node itself must have been visited.


Related Posts:

Nonrecursive Algorithm with Stack to Inorder Traverse Binary Tree