CODEWITHSUNDEEP
algorithmbinary-treebinary-search-treetree-traversal
Ray Rutzer
Ray Rutzer

Reputation: 77

What makes a tree traversal pre-order or in-order?

Why is a tree traversal via root, left and right called pre-order? Shouldn't that be in-order, because the root is always first?

It does not makes sense to me why it is called that way, because the root is always the first element.

Upvotes: 5

Views: 949

Answers (3)

Syed Waris
Syed Waris

Reputation: 1074

Consider this simple tree:

  A
 /  \
B    C

Pre-Order traversal: ABC.

The term contains the word pre. pre means before. So the root is before any of its children. Note that A is before both B and C

Post order Traversal: BCA

The term contains the word post. post means after. So the root is after any of its children. Note that A is after both B and C

Inorder traversal: BAC

The term contains the word In. In means inside (middle). So the root is in middle of its children. Note that A is in between B and C

Upvotes: 0

alseether
alseether

Reputation: 1993

The prefix refers to when the content of the root node should be placed.

enter image description here

Given this tree, you can represent it in various ways:

  • Pre-order: Root is placed first (then left and right children), so the list will look as follows:
[41, 20, 11, 29, 32, 65, 50, 91, 72, 99]
 ^   --------------  ------------------
 |        |                     |
 |        |                     |-----Right sub-tree
 |        | 
 |        |----Left sub-tree
 |
 |------ Root of the tree

Inside left and right sub-tree sublists the preorder is kept.

  • In-order: Left child is placed (analized if you like) first, then root and right child. It will look like this:
[11, 20, 29, 32, 41, 50, 65, 72, 91, 99]
 --------------  |   ------------------
      |          |            |
      |          |            |------- Right sub-tree
      |          |
      |          |---- Root of the tree
      |
      |----- Left sub-tree

Now, first part of the list represents the left sub tree, the root is placed after, and finally, the right sub-tree. Here, inorder is also kept inside left and right sub-trees sublists.

In-order traversal can be seen as a left-to-right scanning.

  • Post-order: Left child analized first, then the right child and finally the root:
[11, 32, 29, 20, 50, 72, 99, 91, 65, 41]
 --------------  ------------------  |
       |                 |           |---- Root of the tree
       |                 |        
       |                 |----- Right sub-tree
       | 
       |------ Left sub-tree

Same as the others, root is at the end, but left and right sublist keep the same postorder property.

Additionally, other posible traversal can be

  • By levels: elements are placed sorted by their level on the tree, left to right
[41, 20, 65, 11, 29, 50, 91, 32, 72, 99]
 |   ------  --------------  ----------
 |      |          |                |-----Level 3
 |      |          |
 |      |          |----- Level 2
 |      |
 |      |------ Level 1
 |
 |----- Level 0 (aka, the root of the tree)

Upvotes: 5

Siong Thye Goh
Siong Thye Goh

Reputation: 3586

We always have the restriction that the left child is visited before the right child.

The main difference is where is the root.

  • If the root is before both children, we call it preorder.(Root, Left, Right)

  • If the root is after both children, we call it postorder. (Left, Right, Root)

  • If the root is in between both children, we call it inorder. (Left, Root, Right)

Upvotes: 8

Related Questions