# Day 23: BST Level-Order Traversal

# Day 23: BST Level-Order Traversal

Terms you'll find helpful in completing today's challenge are outlined below, along with sample Java code (where appropriate).

## Tree Traversal

A *traversal* of some binary tree, , is an algorithm that iterates through each node in exactly time.

## InOrder Traversal

An *inorder* traversal of tree is a recursive algorithm that follows the left subtree; once there are no more left subtrees to process, we process the right subtree. The elements are processed in *left-root-right* order. The basic algorithm is as follows:

```
inOrder(t) {
if(t is not empty) {
inOrder( left subtree of t )
process t's root element
inOrder( right subtree of t )
}
}
```

An inorder traversal of a binary search tree will process the tree's elements in *ascending* order.

## PostOrder Traversal

A *postorder* traversal of tree is a recursive algorithm that follows the left and right subtrees before processing the root element. The elements are processed in *left-right-root* order. The basic algorithm is as follows:

```
postOrder(t) {
if(t is not empty) {
postOrder( left subtree of t )
postOrder( right subtree of t )
process t's root element
}
}
```

## PreOrder Traversal (DFS)

A *preorder* traversal of tree is a recursive algorithm that processes the root and then performs preorder traversals of the left and right subtrees. The elements are processed *root-left-right* order. The basic algorithm is as follows:

```
preOrder(t) {
if(t is not empty) {
process t's root element
preOrder( left subtree of t )
preOrder( right subtree of t )
}
}
```

Because a preorder traversal goes as deeply to the left as possible, it's also known as a *depth-first-search* or *DFS*.

## Level-Order Traversal (BFS)

A *level-order* traversal of tree is a recursive algorithm that processes the root, followed by the children of the root (from left to right), followed by the grandchildren of the root (from left to right), etc. The basic algorithm shown below uses a queue of references to binary trees to keep track of the subtrees at each level:

```
levelOrder(BinaryTree t) {
if(t is not empty) {
// enqueue current root
queue.enqueue(t)
// while there are nodes to process
while( queue is not empty ) {
// dequeue next node
BinaryTree tree = queue.dequeue();
process tree's root;
// enqueue child elements from next level in order
if( tree has non-empty left subtree ) {
queue.enqueue( left subtree of t )
}
if( tree has non-empty right subtree ) {
queue.enqueue( right subtree of t )
}
}
}
}
```

Because a level-order traversal goes level-by-level, it's also known as a *breadth-first-search* (*BFS*).

## Example

The binary tree above has the following traversals:

- InOrder:
`1 2 3 4 5 6 7`

- PostOrder:
`1 3 2 5 7 6 4`

- PreOrder:
`4 2 1 3 6 5 7`

- Level-Order:
`4 2 6 1 3 5 7`