largest smaller BST key

  1##########################################################
  2# CODE INSTRUCTIONS:                                     #
  3# 1) The method findLargestSmallerKey you're asked       #
  4#    to implement is located at line 30.                 #
  5# 2) Use the helper code below to implement it.          #
  6# 3) In a nutshell, the helper code allows you to        #
  7#    to build a Binary Search Tree.                      #
  8# 4) Jump to line 71 to see an example for how the       #
  9#    helper code is used to test findLargestSmallerKey.  #
 10##########################################################
 11
 12# do an in-order traversal
 13# if the current value is greater than num
 14# the previous key was the greatest smaller value
 15
 16
 17# A node 
 18class Node:
 19
 20# Constructor to create a new node
 21  def __init__(self, key):
 22      self.key = key
 23      self.left = None 
 24      self.right = None
 25      self.parent = None
 26
 27# A binary search tree 
 28class BinarySearchTree:
 29
 30  # Constructor to create a new BST
 31  def __init__(self):
 32      self.root = None
 33
 34  def find_largest_smaller_key(self, num):
 35    
 36    def in_order(node):
 37      if solution[0] != n_inf:
 38        return
 39      
 40      if node.left and num < node.key:
 41        in_order(node.left)
 42      
 43      if node.key >= num and solution[0] == n_inf:
 44        solution[0] = prev_value[0]
 45        return
 46
 47      prev_value[0] = node.key
 48      
 49      if node.right and solution[0] == n_inf:
 50        in_order(node.right)
 51        
 52
 53    n_inf = float('-inf')
 54    prev_value = [-1]
 55    solution = [n_inf]
 56    vals = [n_inf, n_inf, n_inf]
 57    in_order(self.root)
 58    if solution[0] == n_inf:
 59      return -1
 60    return solution[0]
 61        
 62  # Given a binary search tree and a number, inserts a
 63  # new node with the given number in the correct place
 64  # in the tree. Returns the new root pointer which the
 65  # caller should then use(the standard trick to avoid
 66  # using reference parameters)
 67  def insert(self, key):
 68
 69      # 1) If tree is empty, create the root
 70      if (self.root is None):
 71          self.root = Node(key)
 72          return
 73
 74      # 2) Otherwise, create a node with the key
 75      #    and traverse down the tree to find where to
 76      #    to insert the new node
 77      currentNode = self.root
 78      newNode = Node(key)
 79
 80      while(currentNode is not None):
 81        if(key < currentNode.key):
 82          if(currentNode.left is None):
 83            currentNode.left = newNode
 84            newNode.parent = currentNode
 85            break
 86          else:
 87            currentNode = currentNode.left
 88        else:
 89          if(currentNode.right is None):
 90            currentNode.right = newNode
 91            newNode.parent = currentNode
 92            break
 93          else:
 94            currentNode = currentNode.right
 95
 96######################################### 
 97# Driver program to test above function #
 98#########################################
 99
100bst  = BinarySearchTree()
101 
102# Create the tree given in the above diagram 
103bst.insert(20)
104bst.insert(9);
105bst.insert(25);
106bst.insert(5);
107bst.insert(12);
108bst.insert(11);  
109bst.insert(14);    
110for i in [5, 17, 25]:
111  result = bst.find_largest_smaller_key(i)
112  print(result)
113
114# Time: best -> O(1) worst -> O(N)
115# Average: (n(n+1)/2/n) -> O(n)
116# Space: best -> O(1) worst -> O(N)
117# Space Average: (n(n+1)/2/n) -> O(n)