bst_from_preorder.py

"""
Constructing a binary search tree from a BST preorder traversel in linear time.

Paulus Schoutsen, Feb 16 2014
"""

import sys

MAX_INT = sys.maxint
MIN_INT = -sys.maxint - 1


class Node(object):
    """ Node in a tree. """

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


def bst_from_preorder(preorder):
    """ Creates a binary search tree from a preorder traversal. """

    # If an empty list is given, return None
    if len(preorder) == 0:
        return None

    # Integers are immutable objects in Python. To share an int between calls
    # a list is being used containing 1 element (the current index).
    index_container = [0]

    return _bst_from_preorder(preorder, index_container,
                              MIN_INT, MAX_INT)


def _bst_from_preorder(preorder, index_container, min_val, max_val):
    """
    Helper method to construct a binary search tree from a preorder traversal.
    """

    # Create the node and increase the current index.
    node = Node(preorder[index_container[0]])
    index_container[0] += 1

    # For both checks, check first if we are not already at the end of preorder

    # If the next value is between min_val and node value then it is the
    # start of the subtree of the left child.
    if index_container[0] < len(preorder) and \
       min_val < preorder[index_container[0]] < node.value:
        node.left = _bst_from_preorder(preorder, index_container,
                                       min_val, node.value)

    # If the next value is between node value and max_val then it is the
    # start of the subtree of the right child.
    if index_container[0] < len(preorder) and \
       node.value < preorder[index_container[0]] < max_val:
        node.right = _bst_from_preorder(preorder, index_container,
                                        node.value, max_val)

    return node


def iter_inorder(node):
    """ Returns a generator that iterates inorder over given tree node. """
    if node.left:
        for value in iter_inorder(node.left):
            yield value

    yield node.value

    if node.right:
        for value in iter_inorder(node.right):
            yield value


if __name__ == "__main__":
    preorder = [10, 5, 1, 7, 40, 50]

    root = bst_from_preorder(preorder)

    # Iterating a BST inorder should generate a sorted list.
    for el in iter_inorder(root):
        print el,

    print ":-)"