Recursive DFS Function not returning every Root to Leaf Path

Question

I am currently trying to make a list of lists with all of the root to leaf paths in a binary tree. When I try writing out the result for the paths list and all of the recursive calls I can't seem to figure out where the error would lie. I thought of the idea of popping off of each individual path after hitting a leaf but that gave weird results as well. I also include the definition of the Tree Node which is the format for the input.

Current input: [1,2,3,null,5](1 is root, 2 and 3 are children of 1, and 5 is the right child of 2) Expected output: [[1,2,3],[1,3]] Current output: [[1,2,5,3],[1,2,5,3]]

Definition for a binary tree node.
 class TreeNode:
 def __init__(self, val=0, left=None, right=None):
 self.val = val
 self.left = left
 self.right = right
def binaryTreePaths(self, root: Optional[TreeNode]):
 if not root:
 return
 paths = []
 def traverse(root,path,paths):
 if not root:
 return []
 path.append(root.val)
 if not root.left and not root.right:
 paths.append(path)
 
 traverse(root.left,path,paths)
 traverse(root.right,path,paths)
 
 
 traverse(root,[],paths)
 return paths

• Samwise: Could you include the code that's needed to run your example and demonstrate the behavior? We could reverse-engineer it but that's a lot of hassle to go to when you could just copy and paste your test data into the question. :)
• learningds: Unfortuntely I don't have the code that runs the function specifically. The expected/current are straight from the system(this is an online problem solving website). The test case is also copied straight from the function input.
• learningds: I added the definition for the input : [1,2,3,null,5]. Each of these in are of the class TreeNode
• Samwise: That's unfortunate, but in that case it's on you to provide runnable code -- in other words you'll need to figure out how to construct a TreeNode tree that matches the test that your code is failing. This should be your first debugging step regardless of whether you're looking for someone else's help.
• learningds: Alright, that makes sense. I will look into creating the Tree and setting up the code. Hopefully I can debug based on that. Thank you for the advice.

Answer 1

If I'm not mistaken, you are doing this LC question. https://leetcode.com/problems/binary-tree-paths/

I have solved this question on LC, so pasting the modified version with comments.

def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
 # for empty root, return empty array
 if not root:
 return []
 # variable to hold all paths
 paths = []
 def traverse(root,path,paths):
 if not root:
 return
 # if root(node) is not empty, this node value will need to be added in current path
 path.append(root.val)
 # if the above node is leaf node,
 # we have to make a copy of path (since list are mutable)
 # and then pop the element of this current path as we back track
 if not root.left and not root.right:
 paths.append(path[:])
 path.pop()
 return 
 # if above node was not leaf node, then travese right and left
 traverse(root.left,path,paths)
 traverse(root.right,path,paths)
 # once traversed, we backtrack by popping
 path.pop()
 traverse(root,[],paths)
 return paths

• learningds: Thank you so much for the comments. This was exactly the question I was attempting(although I was using list of lists instead of strings). I had a few small questions. When handling a lead you use paths.append(path[:]). What does this specific line achieve? Why is is necessary to append a copy of the list and not just the list itself at that given time? Thanks!
• gsb22: As I mentioned in the comments, list is mutable, so when you do the pop in next line, the list containing the path will have element removed as well. So, in the end, you will end up like this [[], []] ,list of empty list.
• gsb22: Also, [start:end], this is called list slicing, If you dont provide, start and end, it slices the whole list and make a copy of it.
• learningds: This makes sense. So in my original code it looks like the copying was giving me issues(I had tried putting in the .pop in several places with no success.) Thank you so much for answering these questions. This was really helpful!