largest smaller BST key

Go Back home

https://www.pramp.com/challenge/pK6A4GA5YES09qKmqG33

I successfully managed this problem. The interviewer was relentless in trying to make me optimise my code, which he succeeded in doing.

  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 
 18 class 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 
 28 class 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 
100 bst  = BinarySearchTree()
101  
102 # Create the tree given in the above diagram 
103 bst.insert(20)
104 bst.insert(9);
105 bst.insert(25);
106 bst.insert(5);
107 bst.insert(12);
108 bst.insert(11);  
109 bst.insert(14);    
110 for 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)