MHB Drawing Trees Through MATHHELPBOARDS: Pre-Order, In-Order, Post-Order

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Drawing Trees
AI Thread Summary
The discussion revolves around tree traversal methods—pre-order, in-order, and post-order—using the string "MATHHELPBOARDS." Participants confirm that the initial traversal attempts are correct but note that there are multiple valid tree structures for these traversals. The conversation highlights that while all trees can be traversed in pre-order and post-order, in-order traversal is specific to binary trees, as it requires distinguishing between left and right children. The participants explore the implications of using different root nodes and how that affects traversal results, particularly questioning the placement of nodes in post-order traversal. Ultimately, they clarify that post-order traversal begins with the leftmost node and proceeds to the right, emphasizing the need for a structured approach when dealing with binary trees.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

I want to draw trees, that traverse "MATHHELPBOARDS" in:

  • pre-order
  • in-order
  • post-order

That's what I have tried:




Could you tell me if it is right or if I have done something wrong? (Thinking)
 

Attachments

  • pre.png
    pre.png
    5.2 KB · Views: 115
  • pre.png
    pre.png
    4.6 KB · Views: 103
  • pre.png
    pre.png
    4.7 KB · Views: 116
Technology news on Phys.org
evinda said:
Hello! (Wave)

I want to draw trees, that traverse "MATHHELPBOARDS" in:

  • pre-order
  • in-order
  • post-order

Hey! (Blush)

All of them are right! (Clapping)

Are they the only possibilities? (Wondering)
 
I like Serena said:
Hey! (Blush)

All of them are right! (Clapping)

(Party) (Happy)

I like Serena said:
Are they the only possibilities? (Wondering)

No, there are more possibilities. An other tree, that traverses "MATHHELPBOARDS" in pre-order is this:

View attachment 3585

Or am I wrong? (Thinking)
 

Attachments

  • preorder.png
    preorder.png
    3.8 KB · Views: 109
evinda said:
No, there are more possibilities. An other tree, that traverses "MATHHELPBOARDS" in pre-order is this:

Or am I wrong? (Thinking)

Nice! (Happy)

I see they are all binary trees.
Do they have to be binary trees? (Wondering)
 
I like Serena said:
Nice! (Happy)

I see they are all binary trees.
Do they have to be binary trees? (Wondering)

I think that it is possible that they are not binary trees.. Am I right? (Thinking)
 
evinda said:
I think that it is possible that they are not binary trees.. Am I right? (Thinking)

We could put the 'M' in the root, and ATHHELPBOARDS as children of the root.
This is pre-order.
Can we also do in-order? (Wondering)
 
I like Serena said:
We could put the 'M' in the root, and ATHHELPBOARDS as children of the root.
This is pre-order.
Can we also do in-order? (Wondering)

Is this a possible tree? (Thinking)

View attachment 3592
Or am I wrong? (Thinking)
 

Attachments

  • in.png
    in.png
    4.3 KB · Views: 103
evinda said:
Is this a possible tree? (Thinking)

I don't think so. (Worried)
Why would M be the first node in this tree? (Wondering)
 
I like Serena said:
I don't think so. (Worried)
Why would M be the first node in this tree? (Wondering)

(Worried) With which node should I start then? :confused:
 
  • #10
evinda said:
(Worried) With which node should I start then? :confused:

Well, I'm assuming that S is the root.
Or isn't it? (Thinking)

So if we do a pre-order traversal, S should be the first letter.
For a post-order traversal, L is the first letter.
And in in-order traversal is not properly defined for a tree that is not binary, but if it was, L would still be the first letter. (Nerd)

How can M be the first letter? (Wondering)
 
  • #11
I like Serena said:
Well, I'm assuming that S is the root.
Or isn't it? (Thinking)

So if we do a pre-order traversal, S should be the first letter.
For a post-order traversal, L is the first letter.
And in in-order traversal is not properly defined for a tree that is not binary, but if it was, L would still be the first letter. (Nerd)

How can M be the first letter? (Wondering)

So, can we just traverse a tree in post-order and in-order, if it is a binary tree?
But.. we can traverse all trees in pre-order?
Or have I understood it wrong? (Thinking)
 
  • #12
evinda said:
So, can we just traverse a tree in post-order and in-order, if it is a binary tree?
But.. we can traverse all trees in pre-order?
Or have I understood it wrong? (Thinking)

We can traverse any tree in both pre-order and post-order.
It's just that in-order requires us to be able to distinguish between left and right.
And we can only do that with a binary tree. (Wasntme)
 
  • #13
I like Serena said:
We can traverse any tree in both pre-order and post-order.
It's just that in-order requires us to be able to distinguish between left and right.
And we can only do that with a binary tree. (Wasntme)

At the post-order, we have this row: left, right, root, right? (Thinking)

So, when we have, for example, this tree:

View attachment 3604

where do we have to put t? :confused:
 

Attachments

  • how.png
    how.png
    2.8 KB · Views: 93
  • #14
evinda said:
At the post-order, we have this row: left, right, root, right? (Thinking)
So, when we have, for example, this tree:

where do we have to put t? :confused:

Post-order would not start wit the 'm', but with the leftmost unlabeled node.
That is, it repeated takes the leftmost branch starting from the root until it encounters a leaf. (Worried)

Once we get to the 'm', the next node is indeed the 'a', and after that its right sibling. (Mmm)
 

Similar threads

MHB How do you draw a binary tree using pre-order and in-order traversal?
Replies
14
Views
3K
What is the order of traversal in this recursive fibonacci function?
Replies
3
Views
2K
MHB Writing an Algorithm to Check Depth of Leaves in an Ordered Tree
2
Replies
65
Views
9K
MHB Which node satisfies this property?
Replies
20
Views
4K
MHB How to Efficiently Merge a Sorted List and a Pre-Order Sorted Tree?
Replies
1
Views
1K
Unsolvable python code bug? (finding the difference between two input strings)
Replies
2
Views
2K
MHB Does Max-Kruskal Algorithm Find the Maximum Spanning Tree?
Replies
1
Views
2K
Tree Creation Via Traversal Output
Replies
1
Views
3K
MHB Deleting Leaf Nodes from an Ordered Binary Tree
Replies
2
Views
1K
Challenge: Find the minimum amount of draws possible for a list of integers
Replies
9
Views
2K

Hot Threads

Recent Insights

Back
Top