Menu
I understand the code behind how to do inorder, preorder, and postorder traversal on a binary search tree. However, I'm confused about the application.
When would you use each? It would be really helpful to illustrate cases of when each method of traversal makes the most sense.
Thanks!
421
Pre-order traverse gives the node values in a sequence of insertion. If you want to create a copy of the tree you need to traverse the source tree in this way. In-order traverse gives the sorted node values. As to post-order traverse you can use this method to delete entire tree cause it visits leaf nodes first.
Uses of Inorder Traversal: In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used. Example: In order traversal for the above-given figure is 4 2 5 1 3.
For Inorder, you traverse from the left subtree to the root then to the right subtree. For Preorder, you traverse from the root to the left subtree then to the right subtree. For Post order, you traverse from the left subtree to the right subtree then to the root.
Inorder Traversal. Inorder Traversal is the one the most used variant of DFS(Depth First Search) Traversal of the tree.
Inorder traversal simply processes the items in the defined order. If, for example, you have a BST of a list of words or names, inorder traversal would print them out in order.
Preorder and postorder traversal most often apply to trees other than binary search trees. For example, to evaluate an expression like A + B * C, you can create a tree like this:
To evaluate the expression, you traverse the tree in postorder, applying each operator to the values from each of its sub-trees.
Preorder traversal could be used for roughly the same purpose if you wanted (for example) to produce output in a language something like Lisp, so the expression should come out as (add A (mul B C)).
70
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
