iterative approach for tree traversal

Question

Can someone help me out with an algorithm to traverse a binary tree iteratively without using any other data structure like a stack

I read somewhere we can have a flag named visited for each node and turn in on if the node is visited but my BinaryTreeNode class does not have a visited variable defined. So I can not potentially do something like node.left.visited = false

Is there any other way to traverse iteratively?

Answer 1

One option would be to thread the binary tree.

Whenever some node points to NULL (be it left or right), make that node point to the node which comes next in its traversal (pre-order, post-order, etc). In this way, you can traverse the entire tree in one iteration.

Sample threaded binary tree:

Note that left node of each node points to the largest value smaller than it. And the right node of each node points to the smallest value larger than it. So this gives an in-order traversal.