## 07/04/2017

### [Java] Binary Tree visits

Given a binary tree, we have many ways of visiting it, depending on our goals:

• BFS: search tree by levels
• DFS inorder: visit root first, then left, then right
• DFS preorder: visit left, then root, then right. Useful to retrieve the tree values in ascending order
• DFS postorder: visit left, then right, then root. Useful when deleting the tree
You can check the code on my Gist.

BFS:

`````` public static List<Integer> BFSVisitList(BST root){
if(root == null) return null;

List<Integer> out = new ArrayList<>();

while(!q.isEmpty()){
BST t = q.remove();
}

return out;
}

public static int[] BFSVisit(BST root){
if(root == null) return null;

int[] res = null;
List<Integer> out = BFSVisitList(root);

if(out != null) res = out.stream().mapToInt(i -> i).toArray();

return res;
}
``````

DFS - inorder:

`````` private static List<Integer> doInorderVisit(BST root, List<Integer> out){
if(root != null){
doInorderVisit(root.left, out);
doInorderVisit(root.right, out);
}
return out;
}

public static List<Integer> inorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);

return out;
}

public static int[] inorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);

return out.stream().mapToInt(i -> i).toArray();
}
``````

DFS - preorder:

`````` private static List<Integer> doPreorderVisit(BST root, List<Integer> out){
if(root != null){
doPreorderVisit(root.left, out);
doPreorderVisit(root.right, out);
}
return out;
}

public static List<Integer> preorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);

return out;
}

public static int[] preorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);

return out.stream().mapToInt(i -> i).toArray();
}
``````

DFS - postorder:

`````` private static List<Integer> doPostorderVisit(BST root, List<Integer> out){
if(root != null){
doPostorderVisit(root.left, out);
doPostorderVisit(root.right, out);
}
return out;
}

public static List<Integer> postorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);

return out;
}

public static int[] postorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);

return out.stream().mapToInt(i -> i).toArray();
}
``````

The code works with Java 8 because converting a List to an array[] is now super simple thanks to the black magic behind list.stream().mapToInt(i -> i).toArray()

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.