# largest smaller BST key

🏠

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
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)