binary tree that serializes [a-zA-Z] into a string with n chars, where n is the number of nodes in the tree

bintree.py

import pprint
import string
import sys

HAS_LEFT_CHILD = 1 << 7
HAS_RIGHT_CHILD = 3 << 6
HAS_BOTH_CHILDREN = 1 << 6
HAS_NO_CHILDREN = ~(3 << 6)


class SerializableBinaryTree(object):
    def __init__(self, value, left=None, right=None):
        if value not in string.letters:
            raise ValueError("Value must be one of [a-zA-Z]!")
        self.left = left
        self.right = right
        self.value = value

    @property
    def serialize(self):
        """
        Recursively serialize the binary tree, encoding the node
        relationships in each value.  Serialized output should be
        equivalent to the number of nodes in the tree.
        """
        byte = ord(self.value)

        if self.left and self.right:
            serialized = chr(byte) + self.left.serialize + self.right.serialize
        elif self.left:
            byte = byte & ~HAS_BOTH_CHILDREN | HAS_LEFT_CHILD
            serialized = chr(byte) + self.left.serialize
        elif self.right:
            byte |= HAS_RIGHT_CHILD
            serialized = chr(byte) + self.right.serialize
        else:
            byte &= HAS_NO_CHILDREN
            serialized = chr(byte)
        return serialized

    @classmethod
    def deserialize(cls, serialized_str, bytes_traversed=0):
        """
        Reconstruct the tree from the serialized string.
        """
        # get the first character of the string
        byte = ord(serialized_str[0])
        # Convert the most significant bits of the char back to 01
        value = chr((byte | (1 << 6)) & ~ (1 << 7))

        if byte >> 6 == 3:
            # only right child
            result = cls.deserialize(serialized_str[1:], bytes_traversed)
            if isinstance(result, tuple):
                bytes_traversed += result[1]
                right = result[0]
            else:
                right = result
            left = None
        elif byte >> 6 == 2:
            # only left child
            result = cls.deserialize(serialized_str[1:], bytes_traversed)
            if isinstance(result, tuple):
                bytes_traversed += result[1]
                left = result[0]
            else:
                left = result
            right = None
        elif byte >> 6 == 1:
            # both left and right child. traverse the left side of the tree
            # first, then skip ahead by the length traversed to the right
            # side of the tree.
            left, bytes_traversed_children = cls.deserialize(
                serialized_str[1:], 1)
            right = cls.deserialize(
                serialized_str[bytes_traversed_children+1:])
            if bytes_traversed:
                bytes_traversed += bytes_traversed_children
        else:
            # no children
            left, right = None, None
        if bytes_traversed > 0:
            return (cls(value, left, right), bytes_traversed)

        return cls(value, left, right)

    @property
    def tree(self):
        tree = {
            'value': self.value,
            'left': self.left.tree if hasattr(self.left, 'tree') else None,
            'right': self.right.tree if hasattr(self.right, 'tree') else None
        }
        return tree

    def print_pretty_tree(self):
        pprint.pprint(self.tree)


def main():
    tree = SerializableBinaryTree(
        value="a",
        left=SerializableBinaryTree(
            value="b",
            left=None,
            right=SerializableBinaryTree("c")),
        right=SerializableBinaryTree(
            value="d",
            left=SerializableBinaryTree(
                value="e",
                right=SerializableBinaryTree(
                    value="f",
                    right=SerializableBinaryTree(
                        value="g"),
                    left=SerializableBinaryTree(
                        value="h")),
                left=None),
            right=None))

    print "Pre-serialized:\n"
    tree.print_pretty_tree()
    print "\nSerialized:" + tree.serialize
    print "Length in serialized form: " + str(len(tree.serialize))
    print "\nDeserialized:\n"
    tree.deserialize(tree.serialize).print_pretty_tree()

if __name__ == "__main__":
    sys.exit(main())

16:18:19-zachwalton~  python bintree.py
Pre-serialized:

{'left': {'left': None,
          'right': {'left': None, 'right': None, 'value': 'c'},
          'value': 'b'},
 'right': {'left': {'left': None,
                    'right': {'left': {'left': None,
                                       'right': None,
                                       'value': 'h'},
                              'right': {'left': None,
                                        'right': None,
                                        'value': 'g'},
                              'value': 'f'},
                    'value': 'e'},
           'right': None,
           'value': 'd'},
 'value': 'a'}

Serialized:a�#��f('
Length in serialized form: 8

Deserialized:

{'left': {'left': None,
          'right': {'left': None, 'right': None, 'value': 'c'},
          'value': 'b'},
 'right': {'left': {'left': None,
                    'right': {'left': {'left': None,
                                       'right': None,
                                       'value': 'h'},
                              'right': {'left': None,
                                        'right': None,
                                        'value': 'g'},
                              'value': 'f'},
                    'value': 'e'},
           'right': None,
           'value': 'd'},
 'value': 'a'}
16:18:27-zachwalton~ 