Successor Binary Tree

tree.py

class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

    def has_no_kids(self):
        return self.right is None and self.left is None

    def has_right(self):
        return not self.right is None

    def has_left(self):
        return not self.left is None

    def has_kids(self):
        return not self.has_no_kids()

    def is_right(self):
        return self.parent.right == self

    def is_left(self):
        return self.parent.left == self

    def __lt__(self, val):
        return self.val < val

    def __gt__(self, val):
        return self.val > val

    def __eq__(self, val):
        return self.val == val

    def __str__(self):
        return "[Node val: %d]" % self.val


class Tree(object):
    def __init__(self):
        self.root = None

    def put(self, val):
        self.root = self._put(self.root, val, None)

    def _put(self, node, val, parent):
        if node is None:
            node = Node(val)
            if isinstance(parent, Node):
                node.parent = parent

        if val < node:
            node.left = self._put(node.left, val, node)
        elif val > node:
            node.right = self._put(node.right, val, node)
        else:
            node.val = val

        return node

    def get(self, val):
        return self._get(self.root, val)

    def _get(self, node, val):
        while not node is None:
            if val < node: node = node.left
            elif val > node: node = node.right
            else: return node

        return None

    def successor(self, val):
        node = self.get(val)

        # Can only have a succesor if has right
        if node == self.root:
            if node.has_right():
                return self.sink_left(node.right).val
            else:
                return None

        # is left node
        elif node.is_left():
            if node.has_no_kids() or node.has_left(): return node.parent.val
            # Go right and then left till None
            if node.has_right():
                return self.sink_left(node.right).val

        # is right node
        elif node.is_right():
            parent = node.parent

            # No right successor possible from self
            # This means we swim up the tree until a left node is found
            # That left nodes parent is the succesor of this right node
            if not node.has_right():
                # parent's parent does not exist aka parent is root
                # no successor
                if parent.parent is None:
                    return None
                else:
                    # parent is a right node
                    # continue up the tree til we have a left node
                    node = self.swim_till_left(node)
                    if node is None:
                        return None
                    return node.parent.val

            # Has a right child
            else:
                return self.sink_left(node.right).val

    # iterate down and left until
    # no left is found
    def sink_left(self, node):
        while not node.left is None:
            node = node.left

        return node

    # iterate up until node is not a right node
    # once the left node is found, return it
    def swim_till_left(self, node):
        while True:
            parent = node.parent

            # No left node found
            if parent is None or parent.parent is None: return None

            # parent is still a right node
            # continue up the tree
            if parent.is_right():
                node = parent
            else:
                return parent

if __name__ == "__main__":
    from sys import stdout
    vals = [30, 25, 20, 26, 14, 28, 8, 15, 27, 29, 52, 49, 63]
    tree = Tree()
    [tree.put(val) for val in vals]

    for val in vals:
        stdout.write("Successor to %d: " % val)
        print tree.successor(val)