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

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. :) — Samwise
– Samwise, Commented Apr 12, 2022 at 3:57
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
– learningds, Commented Apr 12, 2022 at 4:01
I added the definition for the input : [1,2,3,null,5]. Each of these in are of the class TreeNode — learningds
– learningds, Commented Apr 12, 2022 at 4:05
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. — Samwise
– Samwise, Commented Apr 12, 2022 at 4:08
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. — learningds
– learningds, Commented Apr 12, 2022 at 4:12

gsb22 · Accepted Answer · 2022-04-13 03:35:02Z

2

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

edited Apr 13, 2022 at 3:35

answered Apr 12, 2022 at 4:23

gsb22

2,2002 gold badges12 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

learningds Over a year ago

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 Over a year ago

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 Over a year ago

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 Over a year ago

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!

Collectives™ on Stack Overflow

Recursive DFS Function not returning every Root to Leaf Path

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related