Monday, 1 April 2019

Yield all root-to-leaf branches of a Binary Tree

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 traversemethod 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