CODEWITHSUNDEEP
algorithmtreelanguage-agnostictraversaltree-traversal
user8386434
user8386434

Reputation:

Is post-order traversal == bottom-up traversal and pre-order traversal == top-down traversal?

Would it be right to say post-order traversal of a tree should be used to do a bottom-up traversal whereas a pre-order traversal should be used to do a top-down traversal of a binary tree?

This has been true in all the examples that I have encountered, so I just wanted to confirm. There are some problems for which it is intuitive to start from the leaves (at the bottom). Can we use post-order traversal to solve them (and vice versa)?

Thanks!

Upvotes: 0

Views: 4239

Answers (2)

Sai
Sai

Reputation: 1700

No. And actually the terms bottom-up / top-down are generally used for graph, but for trees, it's sort of used as explained below:

  • Preorder traversal: Parents are visited before children and siblings are visited in left-to-right order (might be successively but not always).
  • Postorder traversal: Children are visited before parents and siblings are visited in left-to-right order.
  • Top-down traversal: nodes are visited in the order of non-decreasing depth. Which is basically level-order traversal
  • Bottom-up traversal: This is exactly reverse of top-down traversal

Upvotes: 0

MBo
MBo

Reputation: 80177

No. While post-order traversal and pre-order traversal have clear definition, bottom-up traversal or top-down traversal terms might be interpreted by different ways, they are not generally accepted for binary trees. If anybody uses last terms for trees, exact meaning depends on context.

Look at the picture from wiki:

enter image description here

Does pre-order traversal here look like top-down traversal? Or post-order likes bottom-up traversal? Seems no.

Perhaps you want to consider BFS methods to get level order

Upvotes: 1

Related Questions