Role of left thread in inorder traversal

[zak100]

Homework Statement

Hi,

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

Homework 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)

Follow thread to right, print node (3)

Follow link to right, go to leftmost node and print (5)

Follow thread to right, print node (6)

Follow link to right, go to leftmost node and print (7)

Follow thread to right, print node (8)

Follow link to right, go to leftmost node and print (9)

Follow thread to right, print node (11)

Follow link to right, go to leftmost node and print (13)

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 don't think that there is any role of left thread in inorder traversal.
Some body please guide me.

Zulfi.

 

[haruspex]

i don't think that there is any role of left thread in inorder traversal.

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

 

[zak100]

Hi,
Thanks for your response.
What you mean by reverse order traversal? I don't 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.

 

[haruspex]

What you mean by reverse order traversal?

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

tell me in the context of inorder traversal whether left thread is involved or not?

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.

 

[zak100]

Hi,
Thanks for removing my confusion.
Zulfi.