Trouble printing a generator expression as a list

Question

I am trying to return the values of all the leaves in a binary tree with a generator and putting the yielded values in a list. This is my recursive code that uses yield statements but I don't know how return the finals values with a generator. The second piece of code titled "Previous Code" shows the same code with print statements which outputs the correct values so the only issue is the generator. As a note, this code is using root.left and root.right imported from a Binary Tree class and seems to be working properly. Thank you in advance for any help!!

My code

        def leaves_list(self):
            def find(root):
                if not root:
                    yield
                if not root.left and not root.right:
                    yield root.data
                if root.left:
                    find(root.left)
                if root.right:
                    find(root.right)
            # my attempt
            a = find(self.root)
            lst = []
            for i in a:
                lst.append(next(a))
            return find(self.root)

Previous Code

    def leaves_list(self):
        def find(root):
            if not root:
                return
            if not root.left and not root.right:
                print(root.data, end = " ")
                return
            if root.left:
                find(root.left)
            if root.right:
                find(root.right)
        return find(self.root)

This is my tester code and should be returning the list [5, 1, 8, 4].

Tester Code

root = LinkedBinaryTree.Node(3)
T = LinkedBinaryTree(root)
a = LinkedBinaryTree.Node(2)
a.parent = root
root.left = a
b = LinkedBinaryTree.Node(7)
b.parent = root
root.right = b
c = LinkedBinaryTree.Node(9)
c.parent = a
a.left = c
d = LinkedBinaryTree.Node(5)
d.parent = c
c.left = d
e = LinkedBinaryTree.Node(1)
e.parent = c
c.right = e
f = LinkedBinaryTree.Node(8)
f.parent = b
b.left = f
g = LinkedBinaryTree.Node(4)
g.parent = b
b.right = g

print(T.leaves_list())

This is hard to debug without the tree and node classes, but I'd observe that lst.append(next(a)) should be lst.append(i) As it is you are skipping every other value. — snakecharmerb
– snakecharmerb, Commented Dec 1, 2021 at 7:23
Are you doing this to practice generators, or are you just interested in getting the list? Because the straightforward generator version is inefficient. — Kelly Bundy
– Kelly Bundy, Commented Dec 1, 2021 at 18:54

trincot · Accepted Answer · 2021-12-01 07:53:42Z

2

There are a few issues with your attempt:

find(self.root) is called twice. This should not be necessary as it will do the work twice to get the same result again
lst is created and populated but is never used. You should probably return it.
Don't consume an iterator with both a for loop, and with repeated calls to next(). When you do so, you actually go to the next value twice in each iteration, thereby skipping a value in each iteration.
Consider also that the standard list function already has this feature of creating a list from an iterator.
In the find function you are doing nothing with the value(s) yielded by the recursive call. You should yield them also. You can use the yield from syntax for that.
if not root will not work correctly when the tree really is empty, as the execution still continues after that if block, and so an exception will be raised. You need a return there.
Also, when the tree is empty, there shouldn't be anything that is yielded. An iterator is allowed to just not yield anything, which is appropriate in that case.
Not a problem, but since you have if not root as a base case, you don't really need to check for None before going left or right. So those if conditions can be removed, and the recursive calls can be made unconditionally.

Here is the corrected version:

    def leaves_list(self):
        def find(root):
            if not root:
                return
            if not root.left and not root.right:
                yield root.data
            yield from find(root.left)
            yield from find(root.right)

        return list(find(self.root))

edited Dec 1, 2021 at 7:53

answered Dec 1, 2021 at 7:47

trincot

357k38 gold badges282 silver badges338 bronze badges

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

2 Comments

trincot Over a year ago

That comment might be better placed at the question, since it is the Asker's subject.

Kelly Bundy Over a year ago

I partially did, but then saw your answer's comprehensive list of issues and thought it might fit in there as well.

Nir H. · Accepted Answer · 2021-12-01 07:45:41Z

-1

# my attempt
a = find(self.root)
lst = []
for i in a:
     lst.append(i)
return lst

A shorter alternative:

# my attempt
return list(find(self.root))

edited Dec 1, 2021 at 7:45

answered Dec 1, 2021 at 3:50

Nir H.

5503 silver badges9 bronze badges

Collectives™ on Stack Overflow

Trouble printing a generator expression as a list

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related