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<>();  
   
     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()

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.