CODEWITHSUNDEEP
depth-first-searchinorderpostorder
Saisujithreddy
Saisujithreddy

Reputation: 92

inorder and postorder traversal

What sense does it make to, say, visit children before parent in inorder and postorder? I understand that inorder, preorder and postorder traversal are just a way to represent a tree. Am I correct?

Upvotes: 2

Views: 731

Answers (2)

Ivan
Ivan

Reputation: 427

The Pre-order, In-order, Post-order are three ways to traverse a tree. The above three types of traversal belong to the Depth First traversal.

Take the below picture as an example:

enter image description here

The Depth First Pre-order follows the Node -> Left_Child -> Right-Child convention. And if you use it on our current example, you should get:

A, B, D, E, C

The Depth First In-Order traversal follows the Left-Child -> Node -> Right-Child convention. It looks like this:

D, B, E, A, C

The Depth First Post-Order traversal follows the Left-Node -> Right-Node -> Node convention. That's how it looks:

D, E, B, C, A

The Breadth First Level-Order traversal, is a traversal where you start from the Root Node and go down each level of you tree reading nodes from left to right. It would look like this:

A, B, C, D, E

Upvotes: 0

Viky
Viky

Reputation: 51

In-order, post-order, and pre-order are not ways to represent a tree but ways to traverse the tree. Where it gets interesting is the reasons for choosing one traversal over another.

Pre-order traversals are very useful for duplicating nodes and edges to make a complete duplicate of a binary tree. They are also useful for making prefix expressions (from expression trees.

Using post-order traversals while deleting nodes and values can delete an entire binary tree. Similarly, they can also generate a postfix representation of a binary tree.

Finally, in-order traversals are useful for binary search trees because they return values from the underlying set in order.

Upvotes: 1

Related Questions