class BTNode(object):
        """A node in a binary tree."""

        def __init__(self, item, left=None, right=None):

        """(BTNode, object, BTNode, BTNode) -> NoneType
        Initialize this node to store item and have children left and right,
        as well as depth 0.
        """
        self.item = item
        self.left = left
        self.right = right
        self.depth = 0  # the depth of this node in a tree

    def __str__(self):
        """(BTNode) -> str
        Return a "sideways" representation of the subtree rooted at this node,
        with right subtrees above parents above left subtrees and each node on
        its own line, preceded by as many TAB characters as the node's depth.
        """
        # If there is a right subtree, add an extra TAB character in front of
        # every node in its string representation, with an extra newline at the
        # end (ready to be concatenated with self.item).
        if self.right:
            str_right = "\t" + str(self.right).replace("\n", "\n\t") + "\n"
        else:
            str_right = ""
        # The string representation of self.item: if item is a string, use
        # repr(item) so that quotes are included and special characters are
        # treated correctly -- just like in a list; else use str(item).
        if isinstance(self.item, str):
            str_item = repr(self.item)
        else:
            str_item = str(self.item)
        # If there is a left subtree, add an extra TAB character in front of
        # every node in its string representation, with an extra newline at the
        # beginning (ready to be concatenated with self.item).
        if self.left:
            str_left = "\n\t" + str(self.left).replace("\n", "\n\t")
        else:
            str_left = ""
        # Put the right subtree above the root above the left subtree.
        return str_right + str_item + str_left

    def leaves_and_internals(self):
        """(BTNode) -> ([object], [object])
        Return a pair of lists: (list of all the items stored in the leaves of
        the subtree rooted at this node, list of all the items stored in the
        internal nodes of the subtree rooted at this node).
        """
        #Leaf: Doesn't have children
        #Internal Node: Has children
        leaf = []
        internal = []
        if not self.left and not self.right:
            leaf.append(self.item)
        if self.left is not None:
            internal.append(self.item)
            if self.right is not None:
                self.right.leaves_and_internals()
            self.left.leaves_and_internals()
        elif self.right is not None:
            internal.append(self.item)
            self.right.leaves_and_internals()
        print(leaf, internal)
        return leaf, internal

The BTNode class is starter code given to us where we cannot edit. My responsibility is to write code for leaves_and_intervals by following the docstring given. My only problem currently is not knowing how to use extend to properly combine lists recursively.

My test block looks like so:

if __name__ == "__main__":
    root = BTNode(2, BTNode(4, BTNode(6, BTNode(8, None, None), None), None), None)
    root.leaves_and_internals()

And my output looks like so:

[8] []
[] [6]
[] [4]
[] [2]

The correct output should look like so (order should not matter):

[8] [6, 4, 2]

How do I correctly use extend so that leaf and internal don't keep resetting back to empty list every time it recurses? I know I must have a second set of lists for extend, just not sure how to implement it.

Each time you do append, you're adding the entire object, which in this case is a list. Therefore, you are going to be recursively adding lists. You could try initializing the item/internal empty lists in the class init method instead of each time leaves_internals is called. Then replace your append with extend statements, and that will ensure a single list is intact rather than a list of lists.

This article has been dead for over six months. Start a new discussion instead.