Use fullness of Tree Transversal

, , No Comments

The wikipedia article has a nice concise description of when you would want to use the different types of depth-first search:

  • Pre-order traversal while duplicating nodes and values can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly.
  • In-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).
  • Post-order traversal while deleting or freeing nodes and values can delete or free an entire binary tree. It can also generate a postfix representation of a binary tree.

It boils down to the logistical needs of an algorithm. For example, if you don't use post-order traversal during deletion, then you lose the references you need for deleting the child trees.

0 टिप्पणियाँ:

Post a Comment