Categories

# Binary Tree Traversal

A binary tree is one where each of its nodes has maximum two children nodes. These children are mostly known as Left and Right child.

## 1. In-order Traversal

It goes from left child then current node then right child
So for the given tree above it will be: `[2,17,7,19,3,100,25,36,1]`

```public void inOrder(Node node){
if (node==null) return;
inOrder(node.left);  # repeat this on the left node
visit(node);         # do something at current node
inOrder(node.right); # now work on right node
}```

## 2. Pre-order Traversal

It first deals with current node and goes from left child then right child. So the pre-order traversal is: `[100,19,17,2,7,3,36,25,1] `

```public void preOrder(Node node){
if (node==null) return;
visit(node);         # do something at current node
preOrder(node.left);  # repeat this on the left node
preOrder(node.right); # now work on right node
}```

## 3. Post-order Traversal

It recursively visit left child then right child, and only then the current node in the tree. So for this: `[2,7,17,3,19,25,1,36,100] `

```public void postOrder(Node node){
if (node==null) return;
postOrder(node.left);  # repeat this on the left node
postOrder(node.right); # now work on right node
visit(node);           # do something at current node
}```

## Bonus: Level-order Traversal

Level-order traversal basically is Breadth-First Search (BFS) traversal of a tree. For a BFS, a queue data structure is useful. See the queue implementation here

```public ArrayList<Node> traverse(){
ArrayList<Node> closed = new ArrayList<>();