binary_search_tree.py

# BST is a linked data structure in which each node is an object.
# In addition to a key and satellite data, each node contains attributes left, right, and p
# that point to the nodes corresponding to its left child and its parent.

# BST property
# x is a node in BST if y is any node in a left subtree than y.key <= x.key if y is any node in a right subtree
# than y.key >= x.key


class Node(object):

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


class BST(object):

    def __init__(self):
        self.root = None

    def add(self, key):
        if not self.root:
            self.root = Node(key)
            return
        p = self.root
        while True:
            if key <= p.key:
                if not p.left:
                    p.left = Node(key, p)
                    break
                p = p.left
            else:
                if not p.right:
                    p.right = Node(key, p)
                    break
                p = p.right

    def search(self, x):
        if not self.root:
            return False
        p = self.root
        while True:
            if p.key == x:
                return True
            elif p.key < x and p.left:
                p = p.left
            elif p.key > x and p.right:
                p = p.right
            else:
                return False

    def inorder_tree_walk(self):
        def walk(x):
            if x is not None:
                walk(x.left)
                print(x.key)
                walk(x.right)
        return walk(self.root)

    def iterative_walk(self):
        if not self.root:
            return
        nodes = [self.root]
        while nodes:
            node = nodes.pop()
            print(node.key)
            if node.left:
                nodes.append(node.left)
            if node.right:
                nodes.append(node.right)

    def iterative_inorder(self):
        # 12.1-3
        if not self.root:
            return
        p = self.root.left
        values = []
        while True:
            while p.left:
                p = p.left
            values.append(p.key)
            if p.right:
                p = p.right
            else:
                while p.parent.right == p or not p.parent.right:
                    p = p.parent
                    if not p.right:
                        values.append(p.key)
                    if not p.parent:
                        return values
                values.append(p.parent.key)
                p = p.parent.right