Trees Practice Problems

Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.

1. Implement max_leaf, which takes in a tree and makes a new tree where each node is now the maximum distance away from a leaf node (essentially, each node is now its subtrees maximum height).

def max_leaf(t):
    """Create a new Tree with every node being the maximum distance away that node is from a leaf node. 
    >>>t = Tree(3, [Tree(4), Tree(4, [Tree(1)])])
    >>>new_t = max_leaf(t)
    >>>new_t.entry
    2 # The 3 node was 2 away from the 1 node
    >>>[b.entry for b in new_t.branches]
    [0 1]
    """"
    if not t.branches:
        return Tree(0)
    b = [max_leaf(branch) for branch in t.branches]
    return Tree(max(branch.entry for branch in b) + 1, b)

def max_leaf(t):
    """Create a new Tree with every node being the maximum distance away that node is from a leaf node. 
    >>>t = Tree(3, [Tree(4), Tree(4, [Tree(1)])])
    >>>new_t = max_leaf(t)
    >>>new_t.entry
    2 # The 3 node was 2 away from the 1 node
    >>>[b.entry for b in new_t.branches]
    [0 1]
    """"
    "YOUR CODE HERE"

2. Implement contains, which takes in a tree and an element and outputs True if the tree containts the element, and False otherwise.

def contains(t, elm):
    """Return True if tree contains element, false otherwise.  
    >>>t = Tree(4, [Tree(5), Tree(5, [Tree(6)])])
    >>>contains(t, 6) == True
    True
    >>>contains(t, 1) == False
    True
    """
    if elm == t.entry:
      return True
    if t.branches == []:
      return False
    else: 
      for b in t.branches:
        if contains(b, elm):
          return True
      return False

def contains(t, elm):
    """Return True if tree contains element, false otherwise.  
    >>>t = Tree(4, [Tree(5), Tree(5, [Tree(6)])])
    >>>contains(t, 6) == True
    True
    >>>contains(t, 1) == False
    True
    """
    "YOUR CODE HERE"