4

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?

1 Answer 1

7

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:

enter image description here

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.

2
  • Thanks. How would I go about and implement the same? wont that also require additional variables for successor and predecessors? My BTNode only has three variables, data, left node and right node.
    – Htlcs
    Mar 31, 2014 at 17:36
  • @JimZilla Here is a C implementation of threaded binary tree. It won't require any extra variables in your tree structure and no additional variables for successor and predecessor. Mar 31, 2014 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.