Role of left thread in inorder traversal

  • Thread starter zak100
  • Start date
  • Tags
    Thread
In summary, the conversation discusses the role of left threads in inorder traversal of a threaded binary tree. It is concluded that left threads are not necessary for a standard inorder traversal, but they can be used for a reverse order traversal. The concept of "inorder reverse traversal" is also mentioned, where the left thread would be needed.
  • #1
zak100
462
11

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.
example.jpg
 
Physics news on Phys.org
  • #2
zak100 said:
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.
 
  • #3
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.
 
  • #4
zak100 said:
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
zak100 said:
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.
 
  • #5
Hi,
Thanks for removing my confusion.
Zulfi.
 

Related to Role of left thread in inorder traversal

What is the role of left thread in inorder traversal?

The left thread in inorder traversal is used to maintain the order of traversal in a binary tree. It allows the traversal to move from the current node to its left child, and then to its parent, without having to backtrack to the parent's left subtree.

How does the left thread work in inorder traversal?

The left thread is created by linking the rightmost node in a node's left subtree to itself. This allows the traversal to move to the right without having to backtrack, as the rightmost node in the left subtree is always the next node in the inorder traversal.

Why is the left thread important in inorder traversal?

The left thread is important because it allows for a more efficient and simplified way of traversing a binary tree in inorder. It eliminates the need for recursive calls and backtracking, making the traversal process faster and more optimized.

Can the left thread be used in other types of tree traversals?

Yes, the left thread can be used in other types of tree traversals, such as preorder and postorder. However, it is most commonly used in inorder traversal due to the specific nature of the traversal order.

Are there any limitations to using the left thread in inorder traversal?

The left thread may not be effective for traversing certain types of binary trees, such as skewed or unbalanced trees. In these cases, other traversal methods may be more efficient.

Similar threads

Do we have stack involvement in a threaded tree?
    • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
C: Stack with binary search trees
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Algorithm for computing the depths of all the nodes of tree
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Binary Search Tree Homework - Setup BST & Write Functions
    • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
C: Print specific fields from a structure
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
C: Store The Content Of Linked List Into BST
    • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
Array-list implementation of tree problem
    • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
Finding a Local Minimum in a Complete Binary Tree with Log(N) Probes
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Dynamic allocation of adjacency matrix and traversing a list
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Calculate the time of an all-to-all broadcast for a balanced binary tree (BBT)
    • Engineering and Comp Sci Homework Help
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top