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) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<String> paths = new ArrayList<>();
        backtrack(root, new StringBuilder(), paths);
        return paths;
    }

    private void backtrack(TreeNode root, StringBuilder path, List<String> paths) {
        if (root.left == null && root.right == null) { // Reach a leaf.
            paths.add(path.append(root.val).toString());
            return;
        }
        path.append(root.val).append("->"); // From empty path. Arrow should be appended before reaching leaf.
        int len = path.length();
        if (root.left != null) {
            backtrack(root.left, path, paths);
            path.setLength(len);
        }
        if (root.right != null) {
            backtrack(root.right, path, paths);
            path.setLength(len);
        }
    }

    /**
     * DFS.
     * Recurrence relation:
     * The paths consist of root + all subtrees paths.
     * Base case:
     * If root == null, the resukt list would be empty.
     * If root is a leaf node, then its 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(Integer.toString(root.val));
            return paths;
        }
        // Paths from left subtree.
        for (String path : binaryTreePaths2(root.left)) {
            paths.add(root.val + "->" + path); // Concat root with each path.
        }
        // Paths from right subtree.
        for (String path : binaryTreePaths2(root.right)) {
            paths.add(root.val + "->" + path);
        }
        return paths;
    }
}

@@ -188,16 +188,49 @@
 t;%0A%0A/**%0A
+ * 257. Binary Tree Paths%0A * %3Cp%3E%0A
  * Given
@@ -683,245 +683,379 @@
 d by
-:%0A     * At each node, add its left child's val to the path, traverse the left subtree.%0A     * Then add its right child's val to the path, traverse the right subtree.%0A     * The base case is when we reach a leaf, we add the path to
+ backtracking.%0A     * While backtrack we maintain a current path, and a list of result paths.%0A     * To traverse the tree, we maintain a current tree's root node.%0A     * At each node:%0A     * %7C If it is a leaf, append the value, then add the path to results.%0A     * %7C If not, append the value and an arrow, then backtrack left subtree, reset, backtrack right subtree,
  res
-ul
+e
 t.%0A 
@@ -1122,90 +1122,8 @@
 ) %7B%0A
-        if (root == null) %7B%0A            return Collections.emptyList();%0A        %7D%0A
     
@@ -1328,24 +1328,58 @@
 g%3E paths) %7B%0A
+        if (root == null) return;%0A
         if (
@@ -1428,15 +1428,9 @@
  // 
-Reach a
+A
  lea
@@ -1569,25 +1569,8 @@
 ; //
- From empty path.
  Arr
@@ -1650,45 +1650,8 @@
 ();%0A
-        if (root.left != null) %7B%0A    
     
@@ -1689,36 +1689,32 @@
 paths);%0A        
- 
-   
 path.setLength(l
@@ -1721,62 +1721,32 @@
 en);
-%0A        %7D%0A        if (root.right != null) %7B%0A 
+ // Reset path.%0A
         
    b
@@ -1737,27 +1737,24 @@
 th.%0A        
-   
 backtrack(ro
@@ -1781,28 +1781,24 @@
 s);%0A        
-    
 path.setLeng
@@ -1806,26 +1806,16 @@
 h(len);%0A
-        %7D%0A
     %7D%0A%0A 
@@ -2845,9 +2845,8 @@
 %0A    %7D%0A%7D
-%0A

update 257. Binary Tree Paths