Tree Traversal Explained: In-Order & Post-Order

[esmeco]

COuld someone explain how in order and post order tree traversal work?I've searched through other websites but none of them would explain me in a way I could understand...Thanks in advance for the reply!

 

[mtanti]

Tree traversals should be posted in the programming forum. But I'll explain it here just the same.

OK this is not an easy subject as what is stated has no hard logic. The different modes of traversal of a binary tree (pre order, in order, post order) are different orders of how to read a tree structure such as:

...A
../.\
.B..C

As you can see you cannot read this linearly, you need a way to go up and down the tree. These are the different ways:
Pre order: ABC
In order: BAC
Post order: BCA

What can we see from this? The only thing that is changing is the time when we visit the root node (A) depending on the type of order.

Now why is this? This is because of different ways a binary tree could be structured, for example a tree could sort data out by putting smaller values than the root on the left and larger values on the right. This means that after appending all your data, you could display it all linearly and sorted by using in order traversal as so:

list: 2,1,3
tree:
...2
../.\
1...3
inorder: 1, 2, 3

See? However this is easy because you are using a single root node with 2 attatched nodes. The tree could become enormous but the nodes could be easily retrieved using a traversal mode.

list: 3,6,1,5,2,7,4
tree:
...3
../...\
1...6
..\.../..\
...2..5...7
.../
...4

What is happening here? You first check the root node, if the value to add is smaller than it then go to the left side of the node, if it is greater go the right side and repeat process on the new node found until an empty space is found. This could make sorting frequently inputted data really efficient as the nodes are distributed and so will require less comparisons.

How to traverse it?
You first go as left as possible and you find the smallest value. Going to the furthest right will give you the largest value. Then you go down the nodes and read them either as soon as you meet them (pre order) or after traversing all the left sub tree (in order) or after traversing both left and right sub trees (post order).

EG
...2
.../...\
.1...4
.../...\
...3...5

Pre order: 2, 1, 4, 3, 5
In order: 1 (skipped 2), 2, 3 (skipped 4), 4, 5
Post order: 1 (skipped 2), 3 (skipped 2,4), 5 (skipped 4), 4, 2

How is this done in programming?
You either use recursion or stack. Stack is easier to understand so I'll stick to that. You need a stack (array) to know from where you came. Each node you go into you push into the stack and when you reach the end of a node you pop a previously traversed node back from the stack and see if you need to traverse the next node or if you already did it, in which case you pop another node from the stack. Repeat this until you traversed both subtrees in the root node. You'll find a lot of web sites explaining this using recursion so you shouldn't find a problem, it's the same concept only that the stack is 'built in' in recursion.

If you still didn't understand, post here again.