Trees, trees everywhere ...

gistfile1.py

#!/usr/bin/env python
# (c) Aleksandar Topuzovic <aleksandar.topuzovic@gmail.com>
from functools import partial
from collections import deque

class node(object):
    '''Simple nodee'''
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return "{}".format(self.value)

def print_node(n):
    if n is not None:
        print n

class tree(object):
    '''Simple tree'''
    SENTINEL = '#'

    def __init__(self, root):
        self.root = root

    def _in_order(self, n, func):
        if n is not None:
            self._in_order(n.left, func)
        func(n)
        if n is not None:
            self._in_order(n.right, func)

    def iterative_in_order(self, func=lambda x: print_node(x)):
        stack = deque()
        current = self.root

        while True:
            if current is not None:
                stack.appendleft(current)
                current = current.left
            else:
                if stack:
                    current = stack.popleft()
                    func(current)
                    current = current.right
                else:
                    break

    def in_order(self, func=lambda x: print_node(x)):
        self._in_order(self.root, func)

    def _pre_order(self, n, func):
        func(n)
        if n is not None:
            self._pre_order(n.left, func)
            self._pre_order(n.right, func)

    def iterative_pre_order(self, func=lambda x: print_node(x)):
        stack = deque()
        current = self.root

        while True:
            if current is not None:
                func(current)
                stack.appendleft(current)
                current = current.left
            else:
                if stack:
                    current = stack.popleft()
                    current = current.right
                else:
                    break

    def pre_order(self, func=lambda x: print_node(x)):
        self._pre_order(self.root, func)

    def _post_order(self, n, func):
        if n is not None:
            self._post_order(n.left, func)
            self._post_order(n.right, func)
        func(n)

    def post_order(self, func=lambda x: print_node(x)):
        self._post_order(self.root, func)

    def serialize(self):
        def get_value(list, n):
            if n is None:
                value = tree.SENTINEL
            else:
                value = n.value

            list.append(value)

        nodes = []
        func1 = partial(get_value, nodes)

        self.pre_order(func1)

        return nodes

    def __str__(self):
        def get_value(list, n):
            if n is not None:
                list.append(str(n.value))

        nodes = []
        func1 = partial(get_value, nodes)
        self.pre_order(func1)

        return ', '.join(nodes)

    def deserialize(self, nodes):
        self.root = self._deserialize(nodes)

    def _deserialize(self, nodes):
        value = nodes.pop(0)

        if value == tree.SENTINEL:
            return None

        n = node(value)

        n.left = self._deserialize(nodes)
        n.right = self._deserialize(nodes)
        return n

def build_sample1():
    node1 = node(30)
    node11 = node(10)
    node12 = node(20)
    node111 = node(50)
    node121 = node(45)
    node122 = node(35)

    node1.left = node11
    node1.right = node12
    node11.left = node111
    node12.left = node121
    node12.right = node122

    return tree(node1)


def main():
    t1 = build_sample1()
    print "Tree t1:", t1
    serialized = t1.serialize()
    print serialized
    t2 = tree(None)
    t2.deserialize(serialized)
    print "Tree t2:", t2


if __name__ == '__main__':
    main()