Tree Traversal Summary

Depth-first traversal is easily implemented via a stack, including recursively (via the call stack), while breadth-first traversal is easily implemented via a queue, including corecursively

Depth First Search (DFS)

The recursive solutions are trivial, so this article mainly focuses on iterative solutions.

preorder traversal

inorder traversal

postorder traversal

Application

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.

All the above implementations require call stack space proportional to the height of the tree. In a poorly balanced tree, this can be considerable. We can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree

Breadth First Search (BFS)

Tree Traversal Complexity

BFS:

Time complexity is O(|V|) where |V| is the number of nodes,you need to traverse all nodes.
Space complecity is O(|V|) as well - since at worst case you need to hold all vertices in the queue.

DFS:

Time complexity is again O(|V|), you need to traverse all nodes.
Space complexity - depends on the implementation, a recursive implementation can have a O(h) space complexity [worst case], where h is the maximal depth of your tree.
Using an iterative solution with a stack is actually the same as BFS, just using a stack instead of a queue - so you get both O(|V|) time and space complexity.

Note that the space complexity and time complexity is a bit different for a tree than for a general graphs, because you do not need to maintain a visited set for a tree, and |E| = O(|V|), so the |E| factor is actually redundant for a tree. 

Graph Traversal Complexity

Space complexity

When the number of vertices in the graph is known ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the space complexity can be expressed as  where  is the cardinality of the set of vertices. If the graph is represented by an Adjacency list it occupies  space in memory, while an Adjacency matrix representation occupies .

Time complexity

The time complexity can be expressed as  since every vertex and every edge will be explored in the worst case. Note:  may vary between  and , depending on how sparse the input graph is (assuming that the graph is connected).