class TreeDepthFirstSearch {

    class TreeNode(val data: Int, var left: TreeNode?, var right: TreeNode?)



    fun findPathsRecursive(root: TreeNode, sum: Int): MutableList<MutableList<Int>> {
        var currentPath = mutableListOf<Int>()
        var allPaths = mutableListOf<MutableList<Int>>()

         fun hasSumPath(
            currentNode: TreeNode?,
            sum: Int,
            currentPath: MutableList<Int>,
            allPaths: MutableList<MutableList<Int>>
        ) {
             if (currentNode == null) {
                 return
             }

             currentPath.add(currentNode.data)

             if (currentNode.data == sum && currentNode.left == null && currentNode.right == null) {
                 allPaths.add(currentPath)
             } else {
                 hasSumPath(
                     currentNode.left, sum - currentNode.data, currentPath, allPaths
                 )
                 hasSumPath(
                     currentNode.right, sum - currentNode.data, currentPath, allPaths
                 )
             }
             currentPath.removeAt(currentPath.size-1)
         }

        hasSumPath(root, sum, currentPath, allPaths)
        return allPaths
    }
}