Homework Help: Role of left thread in inorder traversal

1. Apr 8, 2017

zak100

1. The problem statement, all variables and given/known data
Hi,

I want to know is there any role for left thread in inorder traversal.

2. Relevant equations
There is no equation but there is an example image of the tree which is attached. After traversal we would get:
Start at leftmost node, print it (1)

3. The attempt at a solution
The above traversal of threaded binary tree does not show any role of left thread in inorder traversal.
So i dont think that there is any role of left thread in inorder traversal.

Zulfi.

2. Apr 8, 2017

haruspex

I believe the left thread would be used for reverse order traversal. A threaded binary tree can be single threaded or double threaded.

3. Apr 8, 2017

zak100

Hi,
What you mean by reverse order traversal? I dont think its same as inorder. I am just talking about inorder traversal in my question. Kindly tell me in the context of inorder traversal whether left thread is involved or not?

Zulfi.

4. Apr 8, 2017

haruspex

I mean the reverse order from inorder. it allows you to traverse the tree in reverse order.
See http://btechsmartclass.com/DS/U3_T5.html
It depends what you mean by inorder traversal. If you only mean going from first to last then the left thread is not needed, but if you interpret "inorder" as just defining an ordering on the elements then it is valid to want to be able to traverse it in either direction. In that view, it is an "inorder reverse traversal", and the left thread is needed.

5. Apr 8, 2017

zak100

Hi,
Thanks for removing my confusion.
Zulfi.