Menu
This is the explanation in wikipedia: Data-flow analysis
This is a typical iteration order for forward data-flow problems. In reverse-postorder iteration, a node is visited before any of its successor nodes has been visited, except when the successor is reached by a back edge. (Note that this is not the same as preorder.)
Can someone explain this in greater detail?
903
Reason is post order is non-tail recursive ( The statements execute after the recursive call). If you just observe here, postorder traversal is just reverse of preorder traversal (1 3 7 6 2 5 4 if we traverse the right node first and then left node.)
Reverse preorder traversal is a modified version of preorder traversal sometimes needed for solving tree problems. The basic concept for reverse preorder traversal remains exactly same as of the preorder traversal, except the subtree traverse order (which one will be traversed first b/w right and left).
Reverse inorder traversal is a modified version of inorder traversal sometimes needed for solving tree problems. The basic concept for reverse inorder traversal remains exactly same as of the inorder traversal, except the subtree traverse order. In normal inorder traversal we saw that. First, traverse the left subtree.
DFS has both a preorder and postorder traversal. Preorder means we visit the node before visiting its children. Postorder order means we visit the node only after visiting its children.
The basic concept for postorder traversal lies in its name itself. Post means "after" (last/finally) and that's why root is being traversed at last and its subtrees are being traversed first. Reverse postorder traversal is variation of postorder traversal where the subtree order is exact opposite than the normal postorder traversal.
Iterative preorder traversal can be easily implemented using two stacks. The first stack is used to get the reverse postorder traversal. The steps to get a reverse postorder are similar to iterative preorder. You may also like to see a method which uses only one stack.
Reverse Level order traversal of the above tree is “4 5 2 3 1”. Both methods for normal level order traversal can be easily modified to do reverse level order traversal. Recommended: Please solve it on “ PRACTICE ” first, before moving on to the solution.
Preorder traversal of binary tree is 1 2 4 5 3 Inorder traversal of binary tree is 4 2 5 1 3 Postorder traversal of binary tree is 4 5 2 3 1.
Reverse postordering as the name suggests produces the exact opposite of postorder traversal.
Example
For the above referred directed graph
postorder traversals are D B C A and D C B A
reverse postorder traversals are A C B D and A B C D
How to obtain reverse postorder traversal
One way is to run postorder traversal and push the nodes in a stack in postorder.
Then pop out the nodes to get the reverse postorder.
Application
Topological sorting using depth first search.
60
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
