Binary Tree Paths

Source:LeetCode

Solution: We do a preorder traversal add each node in the string followed by an arrow "->" if the current node is a leaf node (have no right or left child) then we add the string to the list, otherwise, we add an arrow and make a recursive call in a preorder fashion. The previous string is stored in stack and we can use it later when the call is returned to add another possible routes from root to the leaf nodes. 


Complexity Analysis

• Time complexity : $O($n). $n$ nodes need to be traversed ($n$ represents the number of nodes in a given tree)$.$
• $$
  

Solution:

 public List<String> binaryTreePaths(TreeNode root) {
        
        ArrayList<String> path = new ArrayList();
        binaryPath(root,"",path);
        return path;         
    }
    public static void binaryPath(TreeNode root,String s,List<String> path){
     
          if(root == null)
                return;
        
           s+=""+root.val;                 
           if(root.left == null && root.right == null) //add string to list if leaf node
               path.add(s);
        
           s+="->"; //add arrow if it's NOT a leaf node
           binaryPath(root.left,s,path); 
           binaryPath(root.right,s,path);    
         }

Solution using StringBuilder:  String in Java is immutable, so every time append the number or arrow it will create a new string object. Thus, StringBuilder will be ideal in this problem as it's mutable.

 public List<String> binaryTreePaths(TreeNode root) {
        
        ArrayList<String> path = new ArrayList();
        StringBuilder sb = new StringBuilder("");
        binaryPath(root,sb,path);
        return path;         
    }
    public static void binaryPath(TreeNode root,StringBuilder sb,List<String> path){
        
        if(root!= null){
             int len = sb.length();
             sb.append(""+root.val);
            
            if(root.left == null && root.right == null)
                path.add(sb.toString());    //add string to list
            
             sb.append("->");
             binaryPath(root.left,sb,path); //preorder traversal
             binaryPath(root.right,sb,path);    
             sb.setLength(len);        //set length back accordingly
        }
        
    }