Returning list of all paths in BST python

Question

Say I have a binary tree with the paths from root to leaf being 3-1-3, 3-4-5, 3-4-1 ... How would I go about returning a list of all the different paths? This is what I have so far, but all it does is return [[3, 1, 3, 4, 1, 5], [3, 1, 3, 4, 1, 5], [3, 1, 3, 4, 1, 5]], which is three lists of all the nodes in the tree instead of a separate list for each path.

self.res = []
def helper(root, temp):
   if not root:
      return
   temp.append(root.val)
   if not root.left and not root.right:
      self.res.append(temp)
      return
   helper(root.left, temp)
   helper(root.right, temp)
helper(root, [])

Sash Sinha · Accepted Answer · 2021-01-29 19:40:51Z

1

You can't append to temp like that you need to create a different copy of the current temp for both the left and right branch recursive calls.

Here is a slightly modified version of your recursive DFS approach that should work as you desire, by doing that:

class BinaryTreePaths:
    def __init__(self):
        self.res = []
    
    def get_binary_tree_paths(self, root):
        if not root:
            return []
        self.helper(root, [])
        return self.res
    
    def helper(self, node, temp):
        if not node.left and not node.right:
            self.res.append(temp + [node.val])
        if node.left:
            self.helper(node.left, temp + [node.val])
        if node.right:
            self.helper(node.right, temp + [node.val])

edited Jan 29, 2021 at 19:40

answered Jan 29, 2021 at 18:36

Sash Sinha

22.8k4 gold badges27 silver badges48 bronze badges

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

Collectives™ on Stack Overflow

Returning list of all paths in BST python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related