Traversal of a Tree

A traversal of a tree $T$ is a systematic way of accessing or visiting all the nodes of $T$ .

There are different traversal schemes, for DST we need to know:

Preorder traversal
Preorder traversal is where a node is visited before its descendants.
- Parents always come before their children.
- Running time for a tree with $n$ nodes is $O (n)$ .
```
def preOrder(T, v):
	visit(v)
	for each child w of v in T:
		preOrder(T, w)
```
Link to original
In-order traversal
In-order traversal (applies to binary trees) is where a node is visited after its left sub-tree and before the right sub-tree.
```
def inOrder(T, v):
	if hasLeft(v):
		inOrder(T, left(v))
 
	visit(v)
 
	if hasRight(v):
		inOrder(T, right(v))
```
Link to original
Postorder traversal
Postorder traversal is where a node is visited after its descendants.
- Running time for a tree with $n$ nodes is $O (n)$ .
```
def postOrder(T, v):
	for each child w of v in T:
		postOrder(T, w)
	visit(v)
```
Link to original