1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Role of left thread in inorder traversal

  1. Apr 8, 2017 #1
    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)

    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)


    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.
    Some body please guide me.

    Zulfi. example.jpg
     
  2. jcsd
  3. Apr 8, 2017 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I believe the left thread would be used for reverse order traversal. A threaded binary tree can be single threaded or double threaded.
     
  4. Apr 8, 2017 #3
    Hi,
    Thanks for your response.
    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.
     
  5. Apr 8, 2017 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  6. Apr 8, 2017 #5
    Hi,
    Thanks for removing my confusion.
    Zulfi.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Role of left thread in inorder traversal
  1. Role of the engineer (Replies: 3)

  2. Kvl on left side (Replies: 6)

Loading...