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

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.