Sorry if this is a common question but I haven't found an appropriate answer for my particular problem. I'm trying to implement a walk
method that walks a binary tree from its root node to each of its leaf nodes, yielding the root-to-leaf path whenever I get to a leaf node. For example, walking the binary tree represented by:
__a__
/ \
b d
/ \ / \
- c - -
Would yield:
['a', 'b', 'c']
['a', 'd']
My idea is that BinaryTree.walk
calls Node.traverse
on the root node, which in turn calls the traverse
method of each child node recursively. BinaryTree.walk
also creates an empty list which is passed around with each traverse
call, appending the data of each node, yielding the list once a leaf node is reached and popping each element out of the list after visiting each node.
At some point, something is going wrong though. This is my code:
class Node:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
def __repr__(self):
return f"{self.__class__.__name__}({self.data})"
@property
def children(self):
return self.left, self.right
def traverse(self, branch):
print('ON NODE:', self)
branch.append(self.data)
if self.left is None and self.right is None:
yield branch
else:
for child in self.children:
if child is not None:
print('ENTERING CHILD:', child)
child.traverse(branch=branch)
print('EXITING CHILD:', child)
branch.pop()
class BinaryTree:
def __init__(self, root=Node()):
if not isinstance(root, Node):
raise ValueError(f"Tree root must be Node, not {type(root)}")
self.root = root
def __repr__(self):
return f"{self.__class__.__name__}({self.root})"
def walk(self):
node = self.root
branch = []
yield from node.traverse(branch=branch)
if __name__ == '__main__':
# create root node
n0 = Node('A')
# create binary tree with root node
tree = BinaryTree(root=n0)
# create others nodes
n1 = Node(data='B')
n2 = Node(data='C')
n3 = Node(data='D')
# connect nodes
n0.left = n1
n0.right = n3
n1.right = n2
# walk tree and yield branches
for branch in tree.walk():
print(branch)
Expected output:
ON NODE: Node(A)
ENTERING CHILD: Node(B)
ON NODE: Node(B)
ENTERING CHILD: Node(C)
ON NODE: Node(C)
['A', 'B', 'C'] # yielded branch
EXITING CHILD: Node(C)
EXITING CHILD: Node(B)
ENTERING CHILD: Node(D)
ON NODE: Node(D)
['A', 'D'] # yielded branch
EXITING CHILD: Node(D)
Actual output:
ON NODE: Node(A)
ENTERING CHILD: Node(B)
EXITING CHILD: Node(B)
ENTERING CHILD: Node(D)
EXITING CHILD: Node(D)
IndexError: pop from empty list
I understand I'm doing something wrong with the list since it's trying to pop when it's empty, but I can't understand how it got to that. It should call pop
once for each append
call.
Also I can't figure out why the nodes are being entered and exited, but the ON NODE:
message is not being printed... It's like my code just skips the child.traverse(branch=branch)
line somehow?
Can anyone help me understand where I'm messing this up?
Thanks in advance for your help!
from Yield all root-to-leaf branches of a Binary Tree
No comments:
Post a Comment