tree traverse recursive in level-first order and depth-first order

Question

Hello, Is there any algorithm can traverse a tree recursively in level-first order and non-recursively in postorder.Thanks a lot.

Answer 1

Wikipedia says,

Traversal

Compared to linear data structures like linked lists and one dimensional arrays, which have only one logical means of traversal, tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed defines the traversal type.

These steps (in no particular order) are: performing an action on the current node (referred to as "visiting" the node), traversing to the left child node, and traversing to the right child node. Thus the process is most easily described through recursion.

To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:

1. Visit the node.
2. Traverse the left subtree.
3. Traverse the right subtree. (This is also called Depth-first traversal.)

To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node:

1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree. (This is also called Symmetric traversal.)

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the node.

Finally, trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This is also called Breadth-first traversal.

Answer 2

You can recurse a tree in post order iteratively by using a stack instead of the implicit call stack used in recursion.

Answer 3

To get an effectively recursive breadth-first search you can use iterative deepening depth-first search. It's particularly good for situations where the branching factor is high, where regular breadth-first search tends to choke from excessive memory consumption.

Edit: Marcos Marin already mentioned it, but for the sake of completeness, the Wikipedia page on breadth-first traversal describes the algorithm thus:

1. Enqueue the root node.
2. Dequeue a node and examine it.
   • If the element sought is found in this node, quit the search and return a result.
   • Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
3. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
4. Repeat from Step 2.

Note: Using a stack instead of a queue would turn this algorithm into a depth-first search.

That last line is, obviously, interesting to you if you want to do a non-recursive depth-first traversal. Getting pre- or post-order is just a matter of modifying how you append the nodes in step 2.b.