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())
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))
# 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))