Successor and Predecessor - Binary Search Tree (Python)

Question

I am trying out this successor and predecessor on Binary search tree.

Just wondering once I get hold of successor code, can I flip it over and use it for predecessor? I've coded the successor, and tried to use it for predecessor. However, my output value doesn't change, even though I tried to place other value..

Below is my code:

Succ

def succ(self, key):
    temp = self.root
    prev = None
    if (temp.right is not None):
        temp  = temp.right
        while (temp.left is not None):
            temp = temp.left
        prev = temp
    elif temp.left is not None:e
        temp = temp.left
        while (temp.right is not None):
            temp = temp.right
        prev = temp
    else:
        return None
    return prev.key

Predecessor

def pred(self, key):
        temp = self.root
        prev = None
        #if right is not none, succ lies in the right sub tree
        if (temp.right is not None):
            temp  = temp.right
            while (temp.left is not None):
                #return the node with the minimum key value
                temp = temp.left
            prev = temp
        #if left not none, succ lies in the right sub tree
        elif temp.left is not None:
            #go right till .right is None
            #return the node with the maximum key value
            temp = temp.left
            while (temp.right is not None):
                temp = temp.right
            prev = temp
        else:
            #no succ
            return None
        return prev.key

the tree

    def createTree(self):
        #root
        self.put("F",6)
        #leftSubTree
        self.put("D",4)
        #leftLeftSubTree
        self.put("C",3)
        self.put("B",2)
        self.put("A",1)
        #LeftRightSubTree
        self.put("E",5)
        #RightSubTree
        self.put("I",9)
        #RightLeftSubTree
        self.put("G",7)
        self.put("H",8)
        #RightRightSubTree
        self.put("J",10)

Answer 1

Let us assume you have a BST node class with three pointers/references: left, right, and parent, which correspond to the left child, right child, and parent of a given node. The only node in the tree which has a parent that points to None would be the root node.

Let us also assume that we have the following BST:

       15
     /     \
    9       20
   / \     /  \
  3   10  17   21
 / \    \
1   5   11

The BST property states that for any given node n, all nodes in n's left sub-tree shall be less than n; and, all nodes in n's right sub-tree shall be greater than n.

To make things easier when implementing the successor and predecessor functions, it is helpful to have auxiliary functions for finding the minimum and maximum node of a given BST or BST sub-tree.

Minimum

def bst_minimum(tree):
  minimum = tree
  while minimum is not None:
    minimum = minimum.left
  return minimum

Maximum

def bst_maximum(tree):
  maximum = tree
  while maximum is not None:
    maximum = maximum.right
  return maximum

For the tree example above, these functions would return 1 for the minimum and 21 for the maximum.

To find the predecessor of a given node, you have to cover a few cases:

1. If the given node has a left sub-tree, then take the maximum of that sub-tree.
2. Otherwise, move up the tree, following parent nodes until either you hit None or you "turn left."

In the second case, if you hit None, that means there is no predecessor. This would be the case for the node with value 1 in the tree above. It would following parent pointers all the way past the root node.

If there is a predecessor, then it will be the first parent node you encounter after making a left turn up the tree. Put another way, it is the parent node whose value is less than the value of the node from which you started. So, node 17 above would return the root node with a value of 15.

Predecessor

def bst_predecessor(tree):
  if tree.left is not None:
    return bst_maximum(tree.left)
  parent = tree.parent
  child = tree
  while parent is not None and child is parent.left:
    child = parent
    parent = child.parent
  return parent

Since the successor is simply the symmetrical operation to predecessor, you can modify predecessor by flipping the various operations. Namely:

1. Instead of checking the left sub-tree and finding the maximum, you want to check the right tree and find its minimum.
2. Otherwise, follow parent nodes until you can't anymore (in which case there is no successor), or you turn right. So, the successor of node 5, would be node 9 in the tree above.

Successor

def bst_successor(tree):
  if tree.right is not None:
    return bst_minimum(tree.right)
  parent = tree.parent
  child = tree
  while parent is not None and child is parent.right:
    child = parent
    parent = child.parent
  return parent

Answer 2

To flip the succ function and turn it into pred, you need to change every left to a right, and every right to a left.

def pred(self, key):
    temp = self.root
    prev = None
    if (temp.left is not None):
        temp  = temp.left
        while (temp.right is not None):
            temp = temp.right
        prev = temp
    elif temp.right is not None:
        temp = temp.right
        while (temp.left is not None):
            temp = temp.left
        prev = temp
    else:
        return None
    return prev.key