binary tree implementation without class

binary_tree.py

from collections import deque


def node(value=None):
    return {'value': value, 'left': None, 'right': None}


def insert(tree, key):
    """
    Insert 'key' into binary tree.

    >>> root = node()
    >>> insert(root, 3)
    >>> root['value'] == 3
    True
    >>> insert(root, 1)
    >>> root['left']['value'] == 1
    True
    >>> insert(root, 2)
    >>> root['left']['right']['value'] == 2
    True
    """
    if not tree['value']:
        tree['value'] = key
        return
    elif tree['value'] == key:
        return

    if key < tree['value']:
        if tree['left']:
            insert(tree['left'], key)
        else:
            tree['left'] = node(key)
    else:
        if tree['right']:
            insert(tree['right'], key)
        else:
            tree['right'] = node(key)


def search(tree, key):
    """
    Search for 'key' in binary tree.

    >>> root = node()
    >>> for x in [3, 2, 4, 1]:
    ...     insert(root, x)
    >>> search(root, 3)
    3
    >>> search(root, 1)
    1
    >>> search(root, 9)
    """
    if tree['value'] == key:
        return tree['value']

    if key < tree['value'] and tree['left']:
        return search(tree['left'], key)
    elif key > tree['value'] and tree['right']:
        return search(tree['right'], key)


def iter_in_order(tree):
    """
    Yield successive leaves in-order.

    >>> root1 = node()
    >>> [leaf['value'] for leaf in iter_in_order(root1)]
    [None]
    >>> root2 = node()
    >>> for x in [4, 2, 6, 3, 1]:
    ...    insert(root2, x)
    >>> [leaf['value'] for leaf in iter_in_order(root2)]
    [1, 2, 3, 4, 6]
    """
    if tree['left']:
        yield from iter_in_order(tree['left'])

    yield tree

    if tree['right']:
        yield from iter_in_order(tree['right'])


def iter_level_order(tree):
    """
    Yield successive leaves in ascending level order, left-to-right.

    >>> root1 = node()
    >>> [leaf['value'] for leaf in iter_level_order(root1)]
    [None]
    >>> root2 = node()
    >>> for x in [4, 2, 6, 3, 1]:
    ...    insert(root2, x)
    >>> [leaf['value'] for leaf in iter_level_order(root2)]
    [4, 2, 6, 1, 3]
    """
    stack = deque()
    stack.append(tree)

    while stack:
        tree = stack.popleft()
        if tree['left']:
            stack.append(tree['left'])
        if tree['right']:
            stack.append(tree['right'])
        yield tree


if __name__ == "__main__":
    import doctest
    doctest.testmod()

binary_tree_class.py

from collections import deque


class BinaryTree(object):

    def __init__(self, value=None):
        self.value = value
        self.left = self.right = None

    def insert(self, key):
        """
        Insert 'key' into binary tree.

        >>> root = BinaryTree()
        >>> root.insert(3)
        >>> root.value == 3
        True
        >>> root.insert(1)
        >>> root.left.value == 1
        True
        >>> root.insert(2)
        >>> root.left.right.value == 2
        True
        """
        if not self.value:
            self.value = key
            return
        elif self.value == key:
            return

        if key < self.value:
            if self.left:
                self.left.insert(key)
            else:
                self.left = BinaryTree(key)
        else:
            if self.right:
                self.right.insert(key)
            else:
                self.right = BinaryTree(key)

    def search(self, key):
        """
        Search for 'key' in binary tree.

        >>> root = BinaryTree()
        >>> for x in [3, 2, 4, 1]:
        ...     root.insert(x)
        >>> root.search(3)
        3
        >>> root.search(1)
        1
        >>> root.search(9)
        """
        if self.value == key:
            return self.value

        if key < self.value and self.left:
            return self.left.search(key)
        elif key > self.value and self.right:
            return self.right.search(key)

    def iter_in_order(self):
        """
        Yield successive leaves in-order.

        >>> root1 = BinaryTree()
        >>> [leaf.value for leaf in root1.iter_in_order()]
        [None]
        >>> root2 = BinaryTree()
        >>> for x in [4, 2, 6, 3, 1]:
        ...    root2.insert(x)
        >>> [leaf.value for leaf in root2.iter_in_order()]
        [1, 2, 3, 4, 6]
        """
        if self.left:
            yield from self.left.iter_in_order()

        yield self

        if self.right:
            yield from self.right.iter_in_order()

    def iter_level_order(self):
        """
        Yield successive leaves in ascending level order, left-to-right.

        >>> root1 = BinaryTree()
        >>> [leaf.value for leaf in root1.iter_level_order()]
        [None]
        >>> root2 = BinaryTree()
        >>> for x in [4, 2, 6, 3, 1]:
        ...    root2.insert(x)
        >>> [leaf.value for leaf in root2.iter_level_order()]
        [4, 2, 6, 1, 3]
        """
        stack = deque()
        stack.append(self)

        while stack:
            tree = stack.popleft()
            if tree.left:
                stack.append(tree.left)
            if tree.right:
                stack.append(tree.right)
            yield tree


if __name__ == "__main__":
    import doctest
    doctest.testmod()