Returning list of all paths in BST python

user_11030586 0
Viewed 132

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, [])
binary-search-tree recursion python
1 Answers

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])
user_63282560
Related