Role of left thread in inorder traversal

  • Thread starter Thread starter zak100
  • Start date Start date
  • Tags Tags
    Thread
Click For Summary

Discussion Overview

The discussion centers on the role of left threads in inorder traversal of threaded binary trees. Participants explore whether left threads are necessary for this specific traversal method and consider alternative interpretations of traversal order.

Discussion Character

  • Homework-related
  • Debate/contested

Main Points Raised

  • One participant questions the role of left threads in inorder traversal, suggesting that they do not play a significant part.
  • Another participant proposes that left threads may be useful for reverse order traversal, distinguishing it from standard inorder traversal.
  • A participant seeks clarification on the concept of reverse order traversal and its relation to inorder traversal, emphasizing the need for context in the discussion.
  • It is suggested that if "inorder" is interpreted strictly as moving from first to last, then left threads are unnecessary; however, if it is viewed as defining an ordering, left threads could be relevant for reverse traversal.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the necessity of left threads in inorder traversal. Multiple competing views are presented regarding the interpretation of traversal orders and the role of left threads.

Contextual Notes

The discussion highlights the ambiguity in defining "inorder traversal" and its implications for the use of left threads, suggesting that different interpretations may lead to different conclusions about their necessity.

zak100
Messages
462
Reaction score
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
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.
 
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.
 
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.
 
Hi,
Thanks for removing my confusion.
Zulfi.
 

Similar threads

Do we have stack involvement in a threaded tree?
  • · Replies 4 ·
Replies
4
Views
2K
C: Stack with binary search trees
  • · Replies 1 ·
Replies
1
Views
3K
Binary Search Tree Homework - Setup BST & Write Functions
  • · Replies 5 ·
Replies
5
Views
3K
Algorithm for computing the depths of all the nodes of tree
  • · Replies 1 ·
Replies
1
Views
3K
C: Print specific fields from a structure
  • · Replies 1 ·
Replies
1
Views
2K
C: Store The Content Of Linked List Into BST
  • · Replies 2 ·
Replies
2
Views
2K
Array-list implementation of tree problem
  • · Replies 3 ·
Replies
3
Views
2K
Finding a Local Minimum in a Complete Binary Tree with Log(N) Probes
  • · Replies 1 ·
Replies
1
Views
2K
MHB Find Next Smallest & Greatest Key in BST
  • · Replies 1 ·
Replies
1
Views
2K
Efficient way to solve truss by hand
  • · Replies 7 ·
Replies
7
Views
4K