# Optimal BST challenge

I was coding the problem here. I think I have solved it, but I ran into time limit exceeded issues. I am new in Competitive Programming, so I was looking for a better, time efficient logic for solving the same.

Time limit: 1 secs

My time: 3.01 secs

The problem in short:

Given the numbers [1 .. N ] to be put in a binary search tree and a sequence of m searches ($$\s_1\$$ , $$\s_2\$$ , . . . , $$\s_m\$$ ), solve the optimal BST problem with the cost as the sum of the distances between every two consecutive searches $$\s_i\$$ and $$\s_{i+1}\$$ on the BST.

Cost(T,S) = Depth($$\s_1\$$) + Distance($$\s_1\$$, $$\s_2\$$) + Distance($$\s_2\$$, $$\s_3\$$) + ... + Distance($$\s_{m-1}\$$, $$\s_m\$$).

import sys

def getLevel(node, data):
if (node.key == data) :
return 1
downlevel= 1+getLevel(node.left, data)
if (downlevel != 0) :
return downlevel
downlevel = 1+getLevel(node.right,data)
return downlevel

def pathToNode(node, path, k):
path.append(node.key)
if node.key == k :
return True
if ((node.left != None and pathToNode(node.left, path, k)) or
(node.right!= None and pathToNode(node.right, path, k))):
return True
path.pop()
return False

def distance(node, x, y):
path1 = []
pathToNode(node, path1, x)
path2 = []
pathToNode(node, path2, y)
i=0
while i<len(path1) and i<len(path2):
if path1[i] != path2[i]:
break
i = i+1
return (len(path1)+len(path2)-2*i)

class newNode:
def __init__(self, item):
self.key=item
self.left = None
self.right = None

def constructTrees(start, end):
list = []
if (start > end) :
list.append(None)
return list
for i in range(start, end + 1):
leftSubtree = constructTrees(start, i - 1)
rightSubtree = constructTrees(i + 1, end)
for j in range(len(leftSubtree)) :
left = leftSubtree[j]
for k in range(len(rightSubtree)):
right = rightSubtree[k]
node=newNode(i)
node.left = left
node.right = right
list.append(node)
return list

if __name__ == '__main__':
b1,c1=input().split(' ')
b1=int(b1)
c1=int(c1)
ar = input()  # 1 3 2 1 2
ar = ar.split(' ')
ar = [int(x) for x in ar]
min= sys.maxsize
totalTreesFrom1toN = constructTrees(1, b1)
for i in range(len(totalTreesFrom1toN)):
dist = getLevel(totalTreesFrom1toN[i],1)-1
for j in range(len(ar)-1):
dist=dist+distance(totalTreesFrom1toN[i], ar[j], ar[j+1])
if(dist<min):
min=dist
print(min)


Can anyone tell me where I can possibly refine the code?

• Links can rot or become broken. Please include a description of the challenge here in your question. – dfhwze Jul 20 '19 at 18:10
• Maybe I don't understand the code, but I don't see how it could work. For example, neither getlevel() nor pathtonode() handle the case where node is None or alternatively don't recurse if node.left or node.right are None. – RootTwo Jul 21 '19 at 4:51
• @RootTwo for pathnode() if node has no left or right child, it will pop the node value and return False signifying that there is no path ahead to go. For getlevel() I think I missed the back recursion condition. Thanks for pointing it out. – Excelsior Jul 21 '19 at 14:56
• @dfhwze yes you are right, I will edit the question accordingly. – Excelsior Jul 21 '19 at 14:59

### Use the properties of a BST

In a BST, if the value being search for is less than the key of the current node, then it is in the left subtree and if the value is greater than the key of the current node, then it is in the right subtree. Your code always searches the left subtree first and then searches the right subtree if needed. This code only searches one subtree:

def pathToNode(node, path, k):
path.append(node.key)
if node.key == k :
return True

elif k < node.key:
if node.left and pathToNode(node.left, path, k):
return True

else:
if node.right and pathToNode(node.right, path, k):
return True

path.pop()
return False


The same applies to getlevel().

distance() determines the path from the root to each node. Then determines the common prefix of each path. This can be simplified as observing that if both nodes are in the same subtree, then the root of the current tree isn't on the path between the nodes.

def distance(node, x, y):
if x < node.key and y < node.key:
return distance(node.left, x, y)

elif node.key < x and node.key < y:
return distance(node.right, x, y)

else:
path1 = []
pathToNode(node, path1, x)
path2 = []
pathToNode(node, path2, y)

return len(path1) + len(path2) - 2


Note: you don't actually need the path of a node, just it's depth.