1

I have some code in Python that is supposed to return all root to leaf paths in a binary tree in the form of a list (Ex. ["1->2->5", "1->3"] ). The original question is from leetcode.

I need help figuring out what is wrong with my code and/or alternative solutions (in Python, preferably). For the example I gave above, my code returns null while it should in fact print the list I gave. I would also appreciate insight as how you approach this problem when you first see the question.

Here is my code: 

    def binaryTreePaths(self, root):
        list1 = []
        if (root == None): 
            return []
        if (root.left == None and root.right == None):
            return list1.append(str(root.val) + "->") 
        if (root.left != None):
            list1.append(self.binaryTreePaths(root.left)) 
        if (root.right != None):
            list1.append(self.binaryTreePaths(root.right))
Jane Sully
  • 3,137
  • 10
  • 48
  • 87
  • Possible duplicate of [Why does append return none in this code?](http://stackoverflow.com/questions/16641119/why-does-append-return-none-in-this-code) – juanpa.arrivillaga Jan 04 '17 at 18:53
  • Possible duplicate of [Why does Python's list.append evaluate to false?](http://stackoverflow.com/questions/1682567/why-does-pythons-list-append-evaluate-to-false) – Prune Jan 04 '17 at 19:08

1 Answers1

14
  • missing return statement
  • lower level recursion returns list, not a single value (i.e. += vs. .append())
  • values in the list returned by the lower level recursion call should be prepended with "root->"

Altogether:

def binaryTreePaths(self, root):
    if root is None: 
        return []
    if (root.left == None and root.right == None):
        return [str(root.val)]
    # if left/right is None we'll get empty list anyway
    return [str(root.val) + '->'+ l for l in 
             self.binaryTreePaths(root.right) + self.binaryTreePaths(root.left)]

UPD: the solution above uses list comprehensions, one of the reasons we love Python so much. Here is the expanded version:

def binaryTreePaths(self, root):
    if root is None: 
        return []
    if (root.left == None and root.right == None):
        return [str(root.val)]

    # subtree is always a list, though it might be empty 
    left_subtree = self.binaryTreePaths(root.left)  
    right_subtree = self.binaryTreePaths(root.right)
    full_subtree = left_subtree + right_subtree  # the last part of comprehension

    list1 = []
    for leaf in full_subtree:  # middle part of the comprehension
        list1.append(str(root.val) + '->'+ leaf)  # the left part 

    return list1
Marat
  • 15,215
  • 2
  • 39
  • 48