Smoke some trees, yo

A tree is an acyclic graph where each node has one or zero parents and zero or more children.

Binary trees

Number of children is always two.

Ordered binary trees

All nodes left of a given node, n, are <= n; all nodes right of n are > n.

Traversal

Pre-order:

1. visit root
2. go left
3. go right

In-order:

1. go left
2. visit root
3. go right

Post-order:

1. go left
2. go right
3. visit root

Level-order (breadth first search) (needs a queue)

1. enqueue root in q
2. while q is not empty
1. n = q.dequeue()
2. visit n
3. if n.left, enqueue(n.left)
4. if n.right, enqueue(n.right)

Note: changing the queue above to a stack will result in pre-order search (also have to swap the order of 2.3 and 2.4)

Of course, rather than using recursion, you can replace the call stack with an actual stack, and then mark the nodes as visited or not.