[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<>();  
   
     Queue<BST> q = new LinkedList<BST>();  
     q.add(root);  
   
     while(!q.isEmpty()){  
       BST t = q.remove();  
       out.add(t.getVal());  
       if(t.left != null) q.add(t.left);  
       if(t.right != null) q.add(t.right);  
     }  
   
     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);  
       out.add(root.getVal());  
       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){  
       out.add(root.getVal());  
       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);  
       out.add(root.getVal());  
     }  
     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()