patternMinor
What is the point of traversing a binary tree in preoder, inorder or postorder?
Viewed 0 times
thewhatpointpreodertraversinginorderbinarytreepostorder
Problem
Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
Solution
Different traversals of a binary tree exist to suffice different data dependencies between the nodes.
Let's have a comparison between different traversals of a tree. Note that aside from in-fix traversal, the tree doesn't have to be binary.
In case of Postorder, we process the descendants of a node before the node itself, meaning that we want to send some data from the descendants to the ancestors to be able to process the ancestors. For example if you want efficiently to calculate for each node $n_i$ the weight of the subtree rooted at $n_i$, which is the sum of the weights of all descendants of $n_i$ including $n_i$.
In case of Preorder, you process the predecessors before the descendants. One use case is broadcasting data to all descendants of each node in the tree. For example, if you want count the number of predecessors of each node with some characteristic, you propagate the counter of each node to its children and each child add one if it has the characteristic itself.
In case of Inorder you might have a left-right order between the nodes of the tree (Example: binary search tree), and might be interested in visiting the elements according to this order (Printing the keys of a binary search tee in ascending order).
Finally, in case of BFS, we consider the tree as levels, level $l_i$ has all vertices with depth $i-1$, which is at distance $i-1$ from the root of an unweighted tree. BFS has a lot of use-cases. Here we are interested in processing all nodes of each level consequently (starting from the smallest level). Most common use cases are the ones where we want to process the closer vertices to the root before the farther ones for example if we want to assign ids to the vertices so that for two vertices $n_i, n_j$ if $i < j$, $n_j$ is not closer to the root than $n_i$.
Note that in some cases you might be interested in two consequent traversals for example a post-order to gather data from the whole tree in the root and a following pre-order to broadcast the data to each node in the tree in total linear time in the size of the tree.
Note In some cases any of the traversals suffices, if all nodes are independent of each other and you are only interested in visiting all nodes of the tree(For example, to calculate the depth of each node you can use BFS or Preorder with no remarkable differences). However, some times you might still be interested in the order you are visiting the nodes even if there is no data-dependencies between the nodes (For example printing mathematical expression in polish notation vs. infix notation. see link).
Note One interesting application is Euler tour technique in parallel computing. By setting the right weights on the right edges you get pre-order, post-order and the depth of the nodes of a tree. see link.
Let's have a comparison between different traversals of a tree. Note that aside from in-fix traversal, the tree doesn't have to be binary.
In case of Postorder, we process the descendants of a node before the node itself, meaning that we want to send some data from the descendants to the ancestors to be able to process the ancestors. For example if you want efficiently to calculate for each node $n_i$ the weight of the subtree rooted at $n_i$, which is the sum of the weights of all descendants of $n_i$ including $n_i$.
In case of Preorder, you process the predecessors before the descendants. One use case is broadcasting data to all descendants of each node in the tree. For example, if you want count the number of predecessors of each node with some characteristic, you propagate the counter of each node to its children and each child add one if it has the characteristic itself.
In case of Inorder you might have a left-right order between the nodes of the tree (Example: binary search tree), and might be interested in visiting the elements according to this order (Printing the keys of a binary search tee in ascending order).
Finally, in case of BFS, we consider the tree as levels, level $l_i$ has all vertices with depth $i-1$, which is at distance $i-1$ from the root of an unweighted tree. BFS has a lot of use-cases. Here we are interested in processing all nodes of each level consequently (starting from the smallest level). Most common use cases are the ones where we want to process the closer vertices to the root before the farther ones for example if we want to assign ids to the vertices so that for two vertices $n_i, n_j$ if $i < j$, $n_j$ is not closer to the root than $n_i$.
Note that in some cases you might be interested in two consequent traversals for example a post-order to gather data from the whole tree in the root and a following pre-order to broadcast the data to each node in the tree in total linear time in the size of the tree.
Note In some cases any of the traversals suffices, if all nodes are independent of each other and you are only interested in visiting all nodes of the tree(For example, to calculate the depth of each node you can use BFS or Preorder with no remarkable differences). However, some times you might still be interested in the order you are visiting the nodes even if there is no data-dependencies between the nodes (For example printing mathematical expression in polish notation vs. infix notation. see link).
Note One interesting application is Euler tour technique in parallel computing. By setting the right weights on the right edges you get pre-order, post-order and the depth of the nodes of a tree. see link.
Context
StackExchange Computer Science Q#101691, answer score: 7
Revisions (0)
No revisions yet.