package com.freetymekiyan.algorithms.level.easy;

import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Given a binary tree, return all root-to-leaf paths.
 * <p>
 * For example, given the following binary tree:
 * <p>
 * |    1
 * |  /   \
 * | 2     3
 * |  \
 * |   5
 * All root-to-leaf paths are:
 * <p>
 * ["1->2->5", "1->3"]
 * <p>
 * Company Tags: Google, Apple, Facebook
 * Tags: Tree, Depth-first Search
 * Similar Problems: (M) Path Sum II
 */
public class BinaryTreePaths {

    /**
     * DFS.
     * The path from root to leaf can be obtained by:
     * At each node, add its left child's val to the path, traverse the left subtree.
     * Then add its right child's val to the path, traverse the right subtree.
     * The base case is when we reach a leaf, we add the path to result.
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root != null) {
            dfs(root, "", paths);
        }
        return paths;
    }

    private void dfs(TreeNode root, String path, List<String> paths) {
        if (root.left == null && root.right == null) {
            paths.add(path + root.val);
        }
        if (root.left != null) {
            dfs(root.left, path + root.val + "->", paths);
        }
        if (root.right != null) {
            dfs(root.right, path + root.val + "->", paths);
        }
    }

    /**
     * DFS.
     * Recurrence relation:
     * The paths consists of root + all subtrees paths.
     * Base case:
     * If root is null, the list would be empty.
     * If the root is a leaf, then itself's value would be in list.
     * <p>
     * Just concatenate root's value with those paths returned from subtrees.
     */
    public List<String> binaryTreePaths2(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<String> paths = new ArrayList<>();
        if (root.left == null && root.right == null) {
            paths.add(root.val + "");
            return paths;
        }

        // Paths from left subtree
        for (String path : binaryTreePaths2(root.left)) {
            paths.add(root.val + "->" + path);
        }

        // Paths from right subtree
        for (String path : binaryTreePaths2(root.right)) {
            paths.add(root.val + "->" + path);
        }

        return paths;
    }
}

@@ -963,119 +963,182 @@
     
-List%3CString%3E paths = new ArrayList%3C%3E();%0A        if (root != null) %7B%0A            dfs(root, %22%22, paths);%0A        %7D
+if (root == null) %7B%0A            return Collections.emptyList();%0A        %7D%0A        List%3CString%3E paths = new ArrayList%3C%3E();%0A        backtrack(root, new StringBuilder(), paths);
 %0A   
@@ -1180,19 +1180,25 @@
 te void 
-dfs
+backtrack
 (TreeNod
@@ -1207,24 +1207,31 @@
 root, String
+Builder
  path, List%3C
@@ -1293,32 +1293,49 @@
 right == null) %7B
+ // Reach a leaf.
 %0A            pat
@@ -1349,31 +1349,212 @@
 path
- + root.val);%0A        %7D
+.append(root.val).toString());%0A            return;%0A        %7D%0A        path.append(root.val).append(%22-%3E%22); // From empty path. Arrow should be appended before reaching leaf.%0A        int len = path.length();
 %0A   
@@ -1591,27 +1591,33 @@
             
-dfs
+backtrack
 (root.left, 
@@ -1624,33 +1624,48 @@
 path
- + root.val + %22-%3E%22, paths
+, paths);%0A            path.setLength(len
 );%0A 
@@ -1723,11 +1723,17 @@
     
-dfs
+backtrack
 (roo
@@ -1749,33 +1749,48 @@
 path
- + root.val + %22-%3E%22, paths
+, paths);%0A            path.setLength(len
 );%0A 
@@ -1877,17 +1877,16 @@
  consist
-s
  of root
@@ -1941,18 +1941,18 @@
 If root 
-is
+==
  null, t
@@ -1954,16 +1954,23 @@
 ll, the 
+resukt 
 list wou
@@ -1992,20 +1992,16 @@
    * If 
-the 
 root is 
@@ -2006,16 +2006,21 @@
 s a leaf
+ node
 , then i
@@ -2025,13 +2025,8 @@
  its
-elf's
  val
@@ -2275,33 +2275,32 @@
 st();%0A        %7D%0A
-%0A
         List%3CStr
@@ -2404,32 +2404,49 @@
   paths.add(
+Integer.toString(
 root.val
  + %22%22);%0A    
@@ -2437,13 +2437,9 @@
 .val
- + %22%22
+)
 );%0A 
@@ -2465,33 +2465,32 @@
 aths;%0A        %7D%0A
-%0A
         // Paths
@@ -2499,32 +2499,33 @@
 rom left subtree
+.
 %0A        for (St
@@ -2605,32 +2605,63 @@
  + %22-%3E%22 + path);
+ // Concat root with each path.
 %0A        %7D%0A%0A    
@@ -2647,33 +2647,32 @@
 path.%0A        %7D%0A
-%0A
         // Paths
@@ -2690,16 +2690,17 @@
  subtree
+.
 %0A       
@@ -2804,25 +2804,24 @@
 ;%0A        %7D%0A
-%0A
         retu

update binary tree paths