Question

PYTHON 3 PLEASE FOLLOW INSTRUCTIONS

COMPLETE CODE

Problem : Complete the function predecessor() to take in an arbitrary node of a BST, and return the value of the predecessor of the given node.

Code : class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
  
def predecessor(node):
# TODO

Answer 1

#first of all you need a parent attribute in node
#otherwise you wont be able to compute the predecessor

class Node:
def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None
    self.parent = None
  
def predecessor(node):
   
     #if node is None its invalid
     if node is None:
          return None
   
     #if it has a left child then the maximum of the left subtree is the answer
     if not(node.left is None):
          root = node.left #going to left subtree
          while not(node.right is None): #finding the maximum value in left subtree
               root = root.right
          return root
   
     #if we dont have a left subtree we traverse up till we get required answer
   
#                    8
#                   / \
#                  6   12    suppose node = 9
#                      /      so it need to traverse upto 8 which is answer
#                     11
#                    /
#                    9
   
     p = node.parent
     c = node
     while ( not(p is None) and c == p.left):
          c = p
          p = p.parent
        
     return p