LeetCode 257. Binary Tree Paths

Question: https://leetcode.com/problems/binary-tree-paths/

For those who are curious, I am following this sheet of Leetcode questions sorted by difficulty starting from the easiest to the hardest. I find most of the questions previously posted are too simple. I am skipping ahead to some harder ones. The question today is not as difficult, but just like the matrix iteration problem. It provides a skeleton in solving many of the tree problems.

I have solved the question both recursively and iteratively. Personally, I find the recursive solution to be more intuitive. For any recursive solution, we just need to imagine if we have had the answer to the subproblem, what should we do to get the solution. In this case, once we have the paths of the left subtree and right subtree, we simply insert our path node value to the beginning of the paths. The only caveat is to pay close attention to corner cases. Ask yourself, what if the root is NULL? what if the root has no left or right children? Once these corner cases are answered, usually for the easier tree-based questions, the solution should be quite obvious.

The iterative solution is based on the Depth First Search (DFS). This is a general way of traversing a graph (note tree is just a graph). DFS works well in this case, because, it goes all the way to the leaves, and once we reach a leaf, we simply append the path recorded so far to the paths list. The trick here is how one keep track of the path along the way. In python, we can simply use Tuple to store that path along with the node when we push the node to the stack. Whenever we pop that node out, we have the path that leading up to that node. Pushing some additional value along with the node is a general technique for many tree-based questions. For example, this can be used to find the level of a tree for any node as well.

I believe breadth first search (BFS) should work as well, but the code would not be as clean.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        # Recursive Solution
#         paths = []
#         if root:
#             if not root.left and not root.right:
#                 paths.append(str(root.val))
#             if root.left:
#                 leftPaths = self.binaryTreePaths(root.left)
#                 for leftPath in leftPaths:
#                     paths.append("{}->{}".format(root.val, leftPath))
#             if root.right:
#                 rightPaths = self.binaryTreePaths(root.right)
#                 for rightPath in rightPaths:
#                     paths.append("{}->{}".format(root.val, rightPath))            
#         return paths

        # Iterative Solution
        stack = []
        paths = []
        if root:
            stack.append((root, "{}".format(root.val)))
            visited = {}
            while stack:
                v, path = stack.pop()
                if v not in visited:
                    if not v.right and not v.left: # We have reached a leaf
                        paths.append(path)
                    if v.right:
                        stack.append((v.right, "{}->{}".format(path, v.right.val)))
                    if v.left:
                        stack.append((v.left, "{}->{}".format(path, v.left.val)))
                    visited[v] = True
        return paths          

Related Questions:
Binary Tree Paths: https://monkeyinvestment.blogspot.com/2020/03/leetcode-257-binary-tree-paths.html