12 Replies - 22603 Views - Last Post: 26 May 2012 - 03:33 PM

#1 ry110891   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 25
  • Joined: 24-May 12

drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 02:02 PM

I have to draw the binary tree given the following postorder and inorder traversals

Postorder: A B C D E F I K J G H

Inorder: C B A E D F H I G K J

I am having a difficult time making sense on how to draw this. I have not been successful thus far.
Is This A Good Question/Topic? 0
  • +

Replies To: drawing binary trees (postorder and inorder traversals)

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 02:08 PM

Some reading material on Tree Traversals. Beyond that, what specific problems or errors are you encountering? And can you show us your good faith efforts?
Was This Post Helpful? 0
  • +
  • -

#3 ry110891   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 25
  • Joined: 24-May 12

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 02:12 PM

i believe H is my root node and C,B,A,E,D,F is the left sub tree and I,G,K,J is the right sub tree. This is my understanding so far on reading definitions and looking at examples but I could be wrong
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 02:14 PM

Draw out the subtree and I'll be happy to double check it.

By the way- are you asking for help on writing a program to do this? Or are you supposed to draw the trees by hand?
Was This Post Helpful? 0
  • +
  • -

#5 ry110891   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 25
  • Joined: 24-May 12

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 02:17 PM

right now for the time being I just have to draw out the trees by hand and explain my reasoning.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 02:18 PM

I'll move this to Computer Science then.

Like I said before- if you draw out the Tree, I'll double check it for you. :)
Was This Post Helpful? 0
  • +
  • -

#7 ry110891   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 25
  • Joined: 24-May 12

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 05:05 PM

http://www.youtube.c...h?v=fZqfkJ-cb28

I dont understand in this video the inorder at h,k. Why wouldnt it be h,e,k,a.
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 05:10 PM

The idea is to evaluate the left child, the current node, then the right child. This is applied recursively though. So the left child is evaluated as left.left, left, left.right. Then the current Node, then evaluate the right node in the same way as the left Node. So h doesn't have a left Node, but it has a right Node- k. Now since e.left has been evaluated, e is the next Node. Now that b.right has been evaluated, we visit a.
Was This Post Helpful? 2
  • +
  • -

#9 ry110891   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 25
  • Joined: 24-May 12

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 07:12 PM

ok so this is what I came up with I attached a photoAttached Image
Was This Post Helpful? 1
  • +
  • -

#10 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 07:24 PM

For in-order, the F should come first, as it is H.left, and F has no left children. Your post-order traversal is correct, though.
Was This Post Helpful? 2
  • +
  • -

#11 ry110891   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 25
  • Joined: 24-May 12

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 09:31 PM

how about now?
Attached Image
Was This Post Helpful? 1
  • +
  • -

#12 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,863
  • Joined: 27-December 08

Re: drawing binary trees (postorder and inorder traversals)

Posted 24 May 2012 - 09:35 PM

Looks good to me!
Was This Post Helpful? 1
  • +
  • -

#13 TechSyndrome   User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 135
  • Joined: 06-May 12

Re: drawing binary trees (postorder and inorder traversals)

Posted 26 May 2012 - 03:33 PM

Hi,

I found a way to learn this a few days ago:

1. There is a a guy on YouTube who explains this to you within 5 minutes on two separate videos (he doesn't have one for in-order, I'll explain that one shortly). Here is the link:My link

2. The way I learnt it was by making my own acronyms:

Pre-order = very. long. road (VLR). In my head, I was thinking about amazon.co.uk, associating the colour orange with pre-order, and also with regards to pre-ordering an item.

Post-order = light. royal. vehicle (LRV). In my head, I think about the Royal Mail/Post Office and how my order will arrive in a small, red, Royal Mail van.

In-order = live. very. right (LVR). I know this one doesn't make much sense, but I coloured it in green, signifying good health.

My acronyms are unlikely to make sense to you, so try making your own, it helps A LOT. In terms of how to do Binary Tree Traversal, if the YouTube videos aren't clear, give me a shout and I'll do my best to explain them to you. But it is very simple, just don't think of it as Binary Tree Traversal, but a small puzzle. Then you should get the pattern.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1