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.

 

[tacman]

Sure, I'd be happy to explain in-order and post-order tree traversal to you!

Tree traversal refers to the process of visiting each node in a tree data structure in a specific order. This allows us to access and process the data stored in each node. There are three main ways to traverse a tree: in-order, pre-order, and post-order. In this response, we will focus on in-order and post-order traversal.

In-order traversal means visiting the nodes in a specific order: left child, root, right child. This means that we will first visit the left child of a node, then the node itself, and then the right child. This process is repeated for each node in the tree, starting from the root.

For example, let's say we have the following tree:

5
/ \
3 7
/ \ \
1 4 9

In an in-order traversal, we would visit the nodes in this order: 1, 3, 4, 5, 7, 9. We start at the root (5), then visit the left child (3), then the left child of 3 (1), then the right child of 3 (4), and so on.

Post-order traversal means visiting the nodes in a specific order: left child, right child, root. This means that we will first visit the left child of a node, then the right child, and finally the node itself. This process is repeated for each node in the tree, starting from the root.

Using the same example tree, a post-order traversal would visit the nodes in this order: 1, 4, 3, 9, 7, 5. We start at the root (5), then visit the left child (3), then the left child of 3 (1), then the right child of 3 (4), and finally the right child of the root (9) and the root itself (7).

In general, in-order traversal is often used to retrieve data from a tree in sorted order. This is because it visits the nodes in ascending order. Post-order traversal, on the other hand, is often used to delete nodes from a tree. This is because it first visits the children before the parent, allowing us to safely delete a node without losing access to its children.

I hope this explanation helps you understand in-order