Application of Recursive Data: Tree Encoding

class BinTree:
    empty = ()

    def __init__(self, label, left=empty, right=empty):
        self.label = label
        self.left = left
        self.right = right

    def __repr__(self):
        if self.left == self.empty and self.right == self.empty:
            return 'BinTree({})'.format(repr(self.label))
        left = 'BinTree.empty' if self.left == self.empty else repr(self.left)
        right = 'BinTree.empty' if self.right == self.empty else repr(self.right)
        return 'BinTree({}, {}, {})'.format(repr(self.label), left, right)

    def is_leaf(self):
        return self.left == self.right == BinTree.empty

# Sample decoding tree from lecture.

CODED_ALPHABET = {
    "A": "1110",
    "B": "101100",
    "C": "01000",
    "D": "11111",
    "E": "011",
    "F": "00110",
    "G": "111100",
    "H": "0101",
    "I": "1100",
    "J": "001011001",
    "K": "0010111",
    "L": "10111",
    "M": "00111",
    "N": "1010",
    "O": "1101",
    "P": "101101",
    "Q": "001011010",
    "R": "1000",
    "S": "1001",
    "T": "000",
    "U": "01001",
    "V": "001010",
    "W": "111101",
    "X": "001011011",
    "Y": "00100",
    "Z": "001011000",
}

def make_encoding_tree(coding_map):
    """An encoding tree that implements CODING_MAP, a dictionary mapping
    characters to strings of 0s and 1s with the prefix property"""
    def add(c, code):
        """Add C to result with encoding CODE."""
        T = result
        for v in code:
            if v == '0':
                if T.left is BinTree.empty:
                    T.left = BinTree(None, BinTree.empty, BinTree.empty)
                T = T.left
            else:
                if T.right is BinTree.empty:
                    T.right = BinTree(None, BinTree.empty, BinTree.empty)
                T = T.right
        T.label = c

    result = BinTree(None, BinTree.empty, BinTree.empty)
    for c, code in coding_map.items():
        add(c, code)
    return result

ENCODING = make_encoding_tree(CODED_ALPHABET)

def decode(msg, encoding):
    """Decode MSG according ENCODING.
    MSG is a string of '0' and '1' characters.
    ENCODING is a prefix tree where leaf nodes contain the
    characters encoded by the path to that leaf.
    >>> decode(encode("THE CAT IN THE HAT", CODED_ALPHABET), ENCODING)
    'THEXCATXINXTHEXHAT'
    """
    result = ""
    k = 0
    def decode1():
        """Decode and return character starting at MSG[k], incrementing
        k to the bit after that character's representation."""
        nonlocal k
        T = encoding
        while T.label is None: # or while not T.is_leaf()
            if msg[k] == '0':
                T = T.left
            else:
                T = T.right
            k += 1
        return T.label

    while k < len(msg):
        result += decode1()
    return result

def encode(msg, coding_map, default="X"):
    """Encode MSG using CODING_MAP, a dictionary mapping characters to
    strings of 0's and 1's.  Any unrecognized characters are replaced by
    DEFAULT, which must be in CODING_MAP."""
    d = coding_map[default]
    return ''.join(map(lambda x: coding_map.get(x, d), msg))