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&lt;len(path1) and i&lt;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 &gt; 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&lt;min):
            min=dist
    print(min)


Can anyone tell me where I can possibly refine the code?
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 &lt; 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 &lt; node.key and y &lt; node.key:
        return distance(node.left, x, y)

    elif node.key &lt; x and node.key &lt; 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.