Optimal BST challenge

Question

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?

• dfhwze: Links can rot or become broken. Please include a description of the challenge here in your question.
• RootTwo: 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.
• Excelsior: @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: @dfhwze yes you are right, I will edit the question accordingly.

Answer 1

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.