Coding challenges on recursion on numbers and lists — MIT problem set

Problem 1Nested Lists: Flatten, Search, and Why Loops Fall Short

Representing Trees with Node Objects

MIT 6.100L Introduction to CS and Programming Using Python, Fall 2022 · Problem set 4, 1.1) Data Representation Practice — tree1, tree2, tree3 · Dr. Ana Bell · CC BY-NC-SA 4.0 · MIT publishes no solution for this set; the worked solution is ours

Build the three trees described below as Node objects and store them in the variables tree1, tree2 and tree3.

A tree is a hierarchical data structure composed of linked nodes. The highest node is called the root, which has branches that link it to other nodes, which are themselves roots of their respective subtrees. MIT's simple example is a tree of eight nodes labelled by their type: a "root" with two "child" nodes; the left "child" has a "child" of its own (with two "leaf" nodes under it) and a "leaf", and the right "child" has a single "leaf".

We can make a few observations:

Each node can hold data: in this example they are holding a string with their node type.
Data is hierarchical: each node has a parent (except the root), each non-leaf node has 1 or more children, and each leaf node has 0 children. We will be using this nomenclature in the rest of the problem set.
Trees are inherently recursive: a root's children nodes are "roots" of other smaller trees (called subtrees).

The Node class. In this problem set, we will be using a provided Node object to represent trees; it is already at the top of your editor. The tree whose root 1 has the left child 2 and the right child 5, where 5 has the left child 7 and the right child 8, can be initialized with the Node object as follows:

example_tree = Node(1, Node(2), Node(5, Node(7), Node(8)))
print(example_tree.get_value())  # 1
print(example_tree.get_left_child().get_value())  # 2
print(example_tree.get_right_child().get_right_child().get_value())  # 8
print(example_tree.get_left_child().get_left_child())  # None

A brief explanation of the Node class:

You can initialize a node with Node(value, left_child, right_child). value holds the value held in the node, left_child optionally holds the Node constructing the left subtree, and right_child does the same for the right subtree. If there is not a subtree, either do not input that parameter or pass in None.
You can get the Node object holding the left or right subtrees with get_left_child() or get_right_child() respectively. If there is no child, this function returns None.
You can get the value held by a Node with get_value().
Printing a Node draws its tree one level per line, with / and a backslash for the branches. print(example_tree) displays:

The trees to build. Create objects accurately representing the data, and put them into the variables tree1, tree2 and tree3. Every node holds an integer, and left and right matter.

Tree 1: the root is 8. Its left child is 2, whose left child is 1 and right child is 6. Its right child is 10, a leaf.
Tree 2: the root is 7. Its left child is 2; that 2 has the leaf 1 as its left child and 5 as its right child, and 5's children are 3 (left) and 6 (right). The root's right child is 9, whose left child is 8 and right child is 10.
Tree 3: the root is 5. Its left child is 3, whose left child is 2 and right child is 4. Its right child is 14; that 14 has the leaf 12 as its left child and 21 as its right child, and 21's children are 20 (left) and 26 (right).

With the trees right, print(tree1) displays

print(tree2) displays

              7              

          /       \          

      2               9      

    /   \           /   \    

  1       5       8       10  

        /   \                

        3   6

and print(tree3) displays

              5              

          /       \          

      3               14      

    /   \           /   \    

  2       4       12       21  

                        /   \

                        20   26

Adapted for the browser: the Node class is pasted into the editor instead of imported from tree.py, and MIT's pictures of the trees are given in words and as what print displays.

# --- given: the Node class from MIT's tree.py (do not edit) ---

class Node:
    def __init__(self, value, left_child=None, right_child=None):
        '''
        Constructs an instance of Node
        Inputs:
            value: An object, the value held by this node
            left_child: A Node object if this node has a left child, None otherwise
            right_child: A Node object if this node has a right child, None otherwise
        '''
        if isinstance(left_child, Node):
            self.left = left_child
        elif left_child == None:
            self.left = None
        else:
            raise TypeError("Left child not an instance of Node")

        if isinstance(right_child, Node):
            self.right = right_child
        elif right_child == None:
            self.right = None
        else:
            raise TypeError("Right child not an instance of Node")

        self.value = value

    def get_left_child(self):
        '''
        Returns this node's left child if present. None otherwise
        '''
        return self.left

    def get_right_child(self):
        '''
        Returns this node's right child if present. None otherwise
        '''
        return self.right

    def get_value(self):
        '''
        Returns the object held by this node
        '''
        return self.value

    def __eq__(self, tree):
        '''
        Overloads the == operator
        Example usage: Node(6, Node(1)) == Node(6, Node(1)) evaluates to True
        Output:
            True or False if the tree is equal or not
        '''
        if not isinstance(tree, Node):
            return False
        return (self.value == tree.value and
                self.left == tree.left and
                self.right == tree.right)

    def __str__(self):
        '''
        Output:
            A well formated string representing the tree (assumes a node can have at most one parent)
        '''
        def set_tier_map(tree,current_tier,tier_map):
            if current_tier not in tier_map:
                tier_map[current_tier] = [tree]
            else:
                tier_map[current_tier].append(tree)
            if tree.get_left_child() is not None:
                set_tier_map(tree.get_left_child(),current_tier+1,tier_map)
            if tree.get_right_child() is not None:
                set_tier_map(tree.get_right_child(),current_tier+1,tier_map)
        tiers = {}
        set_tier_map(self,0,tiers)
        nextTier = [True]
        for key in sorted(tiers,reverse=False):
            current_tier = nextTier[:]
            nextTier = [' ' for i in range(2**(key+1))]
            for tree in tiers[key]:
                i = current_tier.index(True)
                current_tier[i] = str(tree.get_value())
                if tree.get_left_child():
                    nextTier[2*i] = True
                if tree.get_right_child():
                    nextTier[2*i+1] = True
            tiers[key] = current_tier
        max_tier = max(tiers)
        lowest_tier = []
        for i,val in enumerate(tiers[max_tier]):
            lowest_tier.append(val)
            if i < len(tiers[max_tier])-1:
                lowest_tier.append(' ')
        all_tier_strs = [lowest_tier]
        skip,hop = 1,4
        for key in sorted(tiers,reverse=True):
            if key != max_tier:
                new_tier = [' ' for i in lowest_tier]
                arrow_tier = new_tier[:]
                tier_index,new_tier_index = 0,skip
                offset = hop//4
                if key != max_tier-1:
                    offset //= 2
                while new_tier_index < len(new_tier):
                    new_tier[new_tier_index] = tiers[key][tier_index]
                    if tiers[key+1][2*tier_index] != ' ':
                        arrow_tier[new_tier_index-offset] = '/'
                    if tiers[key+1][2*tier_index+1] != ' ':
                        arrow_tier[new_tier_index+offset] = '\\'
                    tier_index += 1
                    new_tier_index += hop
                skip = hop - 1
                hop = 2*hop
                all_tier_strs.append(arrow_tier)
                all_tier_strs.append(new_tier)

        out = []
        for t in all_tier_strs:
            out.append(' '.join(t))
        return '\n\n'.join(out[::-1])

# --- end of given code ---


# Part A0: Data representation
# Fill out the following variables correctly.
tree1 = None
tree2 = None
tree3 = None

# --- given: the Node class from MIT's tree.py (do not edit) ---

class Node:
    def __init__(self, value, left_child=None, right_child=None):
        '''
        Constructs an instance of Node
        Inputs:
            value: An object, the value held by this node
            left_child: A Node object if this node has a left child, None otherwise
            right_child: A Node object if this node has a right child, None otherwise
        '''
        if isinstance(left_child, Node):
            self.left = left_child
        elif left_child == None:
            self.left = None
        else:
            raise TypeError("Left child not an instance of Node")

        if isinstance(right_child, Node):
            self.right = right_child
        elif right_child == None:
            self.right = None
        else:
            raise TypeError("Right child not an instance of Node")

        self.value = value

    def get_left_child(self):
        '''
        Returns this node's left child if present. None otherwise
        '''
        return self.left

    def get_right_child(self):
        '''
        Returns this node's right child if present. None otherwise
        '''
        return self.right

    def get_value(self):
        '''
        Returns the object held by this node
        '''
        return self.value

    def __eq__(self, tree):
        '''
        Overloads the == operator
        Example usage: Node(6, Node(1)) == Node(6, Node(1)) evaluates to True
        Output:
            True or False if the tree is equal or not
        '''
        if not isinstance(tree, Node):
            return False
        return (self.value == tree.value and
                self.left == tree.left and
                self.right == tree.right)

    def __str__(self):
        '''
        Output:
            A well formated string representing the tree (assumes a node can have at most one parent)
        '''
        def set_tier_map(tree,current_tier,tier_map):
            if current_tier not in tier_map:
                tier_map[current_tier] = [tree]
            else:
                tier_map[current_tier].append(tree)
            if tree.get_left_child() is not None:
                set_tier_map(tree.get_left_child(),current_tier+1,tier_map)
            if tree.get_right_child() is not None:
                set_tier_map(tree.get_right_child(),current_tier+1,tier_map)
        tiers = {}
        set_tier_map(self,0,tiers)
        nextTier = [True]
        for key in sorted(tiers,reverse=False):
            current_tier = nextTier[:]
            nextTier = [' ' for i in range(2**(key+1))]
            for tree in tiers[key]:
                i = current_tier.index(True)
                current_tier[i] = str(tree.get_value())
                if tree.get_left_child():
                    nextTier[2*i] = True
                if tree.get_right_child():
                    nextTier[2*i+1] = True
            tiers[key] = current_tier
        max_tier = max(tiers)
        lowest_tier = []
        for i,val in enumerate(tiers[max_tier]):
            lowest_tier.append(val)
            if i < len(tiers[max_tier])-1:
                lowest_tier.append(' ')
        all_tier_strs = [lowest_tier]
        skip,hop = 1,4
        for key in sorted(tiers,reverse=True):
            if key != max_tier:
                new_tier = [' ' for i in lowest_tier]
                arrow_tier = new_tier[:]
                tier_index,new_tier_index = 0,skip
                offset = hop//4
                if key != max_tier-1:
                    offset //= 2
                while new_tier_index < len(new_tier):
                    new_tier[new_tier_index] = tiers[key][tier_index]
                    if tiers[key+1][2*tier_index] != ' ':
                        arrow_tier[new_tier_index-offset] = '/'
                    if tiers[key+1][2*tier_index+1] != ' ':
                        arrow_tier[new_tier_index+offset] = '\\'
                    tier_index += 1
                    new_tier_index += hop
                skip = hop - 1
                hop = 2*hop
                all_tier_strs.append(arrow_tier)
                all_tier_strs.append(new_tier)

        out = []
        for t in all_tier_strs:
            out.append(' '.join(t))
        return '\n\n'.join(out[::-1])

# --- end of given code ---


# Part A0: Data representation
# Fill out the following variables correctly.
tree1 = None
tree2 = None
tree3 = None

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 3Examples — click to expand

tree1 prints as MIT's Tree 1 (MIT's test_data_representation)

tree2 prints as MIT's Tree 2 (MIT's test_data_representation)

tree3 prints as MIT's Tree 3 (MIT's test_data_representation)

Hidden tests · 3Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3

Representing Trees with Node Objects

Build the three trees described below as Node objects and store them in the variables tree1, tree2 and tree3.

We can make a few observations:

Each node can hold data: in this example they are holding a string with their node type.
Data is hierarchical: each node has a parent (except the root), each non-leaf node has 1 or more children, and each leaf node has 0 children. We will be using this nomenclature in the rest of the problem set.
Trees are inherently recursive: a root's children nodes are "roots" of other smaller trees (called subtrees).

example_tree = Node(1, Node(2), Node(5, Node(7), Node(8)))
print(example_tree.get_value())  # 1
print(example_tree.get_left_child().get_value())  # 2
print(example_tree.get_right_child().get_right_child().get_value())  # 8
print(example_tree.get_left_child().get_left_child())  # None

A brief explanation of the Node class:

You can initialize a node with Node(value, left_child, right_child). value holds the value held in the node, left_child optionally holds the Node constructing the left subtree, and right_child does the same for the right subtree. If there is not a subtree, either do not input that parameter or pass in None.
You can get the Node object holding the left or right subtrees with get_left_child() or get_right_child() respectively. If there is no child, this function returns None.
You can get the value held by a Node with get_value().
Printing a Node draws its tree one level per line, with / and a backslash for the branches. print(example_tree) displays:

The trees to build. Create objects accurately representing the data, and put them into the variables tree1, tree2 and tree3. Every node holds an integer, and left and right matter.

Tree 1: the root is 8. Its left child is 2, whose left child is 1 and right child is 6. Its right child is 10, a leaf.
Tree 2: the root is 7. Its left child is 2; that 2 has the leaf 1 as its left child and 5 as its right child, and 5's children are 3 (left) and 6 (right). The root's right child is 9, whose left child is 8 and right child is 10.
Tree 3: the root is 5. Its left child is 3, whose left child is 2 and right child is 4. Its right child is 14; that 14 has the leaf 12 as its left child and 21 as its right child, and 21's children are 20 (left) and 26 (right).

With the trees right, print(tree1) displays

print(tree2) displays

              7              

          /       \          

      2               9      

    /   \           /   \    

  1       5       8       10  

        /   \                

        3   6

and print(tree3) displays

              5              

          /       \          

      3               14      

    /   \           /   \    

  2       4       12       21  

                        /   \

                        20   26

Adapted for the browser: the Node class is pasted into the editor instead of imported from tree.py, and MIT's pictures of the trees are given in words and as what print displays.

# --- given: the Node class from MIT's tree.py (do not edit) ---

class Node:
    def __init__(self, value, left_child=None, right_child=None):
        '''
        Constructs an instance of Node
        Inputs:
            value: An object, the value held by this node
            left_child: A Node object if this node has a left child, None otherwise
            right_child: A Node object if this node has a right child, None otherwise
        '''
        if isinstance(left_child, Node):
            self.left = left_child
        elif left_child == None:
            self.left = None
        else:
            raise TypeError("Left child not an instance of Node")

        if isinstance(right_child, Node):
            self.right = right_child
        elif right_child == None:
            self.right = None
        else:
            raise TypeError("Right child not an instance of Node")

        self.value = value

    def get_left_child(self):
        '''
        Returns this node's left child if present. None otherwise
        '''
        return self.left

    def get_right_child(self):
        '''
        Returns this node's right child if present. None otherwise
        '''
        return self.right

    def get_value(self):
        '''
        Returns the object held by this node
        '''
        return self.value

    def __eq__(self, tree):
        '''
        Overloads the == operator
        Example usage: Node(6, Node(1)) == Node(6, Node(1)) evaluates to True
        Output:
            True or False if the tree is equal or not
        '''
        if not isinstance(tree, Node):
            return False
        return (self.value == tree.value and
                self.left == tree.left and
                self.right == tree.right)

    def __str__(self):
        '''
        Output:
            A well formated string representing the tree (assumes a node can have at most one parent)
        '''
        def set_tier_map(tree,current_tier,tier_map):
            if current_tier not in tier_map:
                tier_map[current_tier] = [tree]
            else:
                tier_map[current_tier].append(tree)
            if tree.get_left_child() is not None:
                set_tier_map(tree.get_left_child(),current_tier+1,tier_map)
            if tree.get_right_child() is not None:
                set_tier_map(tree.get_right_child(),current_tier+1,tier_map)
        tiers = {}
        set_tier_map(self,0,tiers)
        nextTier = [True]
        for key in sorted(tiers,reverse=False):
            current_tier = nextTier[:]
            nextTier = [' ' for i in range(2**(key+1))]
            for tree in tiers[key]:
                i = current_tier.index(True)
                current_tier[i] = str(tree.get_value())
                if tree.get_left_child():
                    nextTier[2*i] = True
                if tree.get_right_child():
                    nextTier[2*i+1] = True
            tiers[key] = current_tier
        max_tier = max(tiers)
        lowest_tier = []
        for i,val in enumerate(tiers[max_tier]):
            lowest_tier.append(val)
            if i < len(tiers[max_tier])-1:
                lowest_tier.append(' ')
        all_tier_strs = [lowest_tier]
        skip,hop = 1,4
        for key in sorted(tiers,reverse=True):
            if key != max_tier:
                new_tier = [' ' for i in lowest_tier]
                arrow_tier = new_tier[:]
                tier_index,new_tier_index = 0,skip
                offset = hop//4
                if key != max_tier-1:
                    offset //= 2
                while new_tier_index < len(new_tier):
                    new_tier[new_tier_index] = tiers[key][tier_index]
                    if tiers[key+1][2*tier_index] != ' ':
                        arrow_tier[new_tier_index-offset] = '/'
                    if tiers[key+1][2*tier_index+1] != ' ':
                        arrow_tier[new_tier_index+offset] = '\\'
                    tier_index += 1
                    new_tier_index += hop
                skip = hop - 1
                hop = 2*hop
                all_tier_strs.append(arrow_tier)
                all_tier_strs.append(new_tier)

        out = []
        for t in all_tier_strs:
            out.append(' '.join(t))
        return '\n\n'.join(out[::-1])

# --- end of given code ---


# Part A0: Data representation
# Fill out the following variables correctly.
tree1 = None
tree2 = None
tree3 = None

# --- given: the Node class from MIT's tree.py (do not edit) ---

class Node:
    def __init__(self, value, left_child=None, right_child=None):
        '''
        Constructs an instance of Node
        Inputs:
            value: An object, the value held by this node
            left_child: A Node object if this node has a left child, None otherwise
            right_child: A Node object if this node has a right child, None otherwise
        '''
        if isinstance(left_child, Node):
            self.left = left_child
        elif left_child == None:
            self.left = None
        else:
            raise TypeError("Left child not an instance of Node")

        if isinstance(right_child, Node):
            self.right = right_child
        elif right_child == None:
            self.right = None
        else:
            raise TypeError("Right child not an instance of Node")

        self.value = value

    def get_left_child(self):
        '''
        Returns this node's left child if present. None otherwise
        '''
        return self.left

    def get_right_child(self):
        '''
        Returns this node's right child if present. None otherwise
        '''
        return self.right

    def get_value(self):
        '''
        Returns the object held by this node
        '''
        return self.value

    def __eq__(self, tree):
        '''
        Overloads the == operator
        Example usage: Node(6, Node(1)) == Node(6, Node(1)) evaluates to True
        Output:
            True or False if the tree is equal or not
        '''
        if not isinstance(tree, Node):
            return False
        return (self.value == tree.value and
                self.left == tree.left and
                self.right == tree.right)

    def __str__(self):
        '''
        Output:
            A well formated string representing the tree (assumes a node can have at most one parent)
        '''
        def set_tier_map(tree,current_tier,tier_map):
            if current_tier not in tier_map:
                tier_map[current_tier] = [tree]
            else:
                tier_map[current_tier].append(tree)
            if tree.get_left_child() is not None:
                set_tier_map(tree.get_left_child(),current_tier+1,tier_map)
            if tree.get_right_child() is not None:
                set_tier_map(tree.get_right_child(),current_tier+1,tier_map)
        tiers = {}
        set_tier_map(self,0,tiers)
        nextTier = [True]
        for key in sorted(tiers,reverse=False):
            current_tier = nextTier[:]
            nextTier = [' ' for i in range(2**(key+1))]
            for tree in tiers[key]:
                i = current_tier.index(True)
                current_tier[i] = str(tree.get_value())
                if tree.get_left_child():
                    nextTier[2*i] = True
                if tree.get_right_child():
                    nextTier[2*i+1] = True
            tiers[key] = current_tier
        max_tier = max(tiers)
        lowest_tier = []
        for i,val in enumerate(tiers[max_tier]):
            lowest_tier.append(val)
            if i < len(tiers[max_tier])-1:
                lowest_tier.append(' ')
        all_tier_strs = [lowest_tier]
        skip,hop = 1,4
        for key in sorted(tiers,reverse=True):
            if key != max_tier:
                new_tier = [' ' for i in lowest_tier]
                arrow_tier = new_tier[:]
                tier_index,new_tier_index = 0,skip
                offset = hop//4
                if key != max_tier-1:
                    offset //= 2
                while new_tier_index < len(new_tier):
                    new_tier[new_tier_index] = tiers[key][tier_index]
                    if tiers[key+1][2*tier_index] != ' ':
                        arrow_tier[new_tier_index-offset] = '/'
                    if tiers[key+1][2*tier_index+1] != ' ':
                        arrow_tier[new_tier_index+offset] = '\\'
                    tier_index += 1
                    new_tier_index += hop
                skip = hop - 1
                hop = 2*hop
                all_tier_strs.append(arrow_tier)
                all_tier_strs.append(new_tier)

        out = []
        for t in all_tier_strs:
            out.append(' '.join(t))
        return '\n\n'.join(out[::-1])

# --- end of given code ---


# Part A0: Data representation
# Fill out the following variables correctly.
tree1 = None
tree2 = None
tree3 = None

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 3Examples — click to expand

tree1 prints as MIT's Tree 1 (MIT's test_data_representation)

tree2 prints as MIT's Tree 2 (MIT's test_data_representation)

tree3 prints as MIT's Tree 3 (MIT's test_data_representation)

Hidden tests · 3Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3