# Complexity for find pairs with sum - BST

I have written an algorithm for find all the pairs in a BST which have a given sum.

def getPairsForSum(rootNode : Node, expectedSum : Int) : List[(Node,Node)] = {
def check(node1 : Node, node2 : Node) : List[(Node,Node)] = {
if (node1 == null || node2 == null) Nil
else {
val actualSum = node1.value + node2.value
if (actualSum == expectedSum) {
List((node1, node2))
} else if (actualSum > expectedSum) {
check(max(node1, node2).leftNode, min(node1, node2)):::
check(min(node1, node2).leftNode, max(node1, node2))
} else {
check(max(node1, node2).rightNode, min(node1, node2)):::
check(min(node1, node2).rightNode, max(node1, node2))
}
}
}
if(rootNode.value > expectedSum/2) check(rootNode, rootNode.leftNode)
else check(rootNode,rootNode.rightNode)
}

It works well (though gives nodes like (n1,n2) and (n2,n1) in the result). I would like to know the complexity of this algorithm. I am not sure how do I approach calculating time complexity. Is this algorithm better than n square??

EDIT Assuming that this bst does not allow duplicates.

• I think it's better to right algorithm in pseudocode and explain what functions do. – rus9384 Mar 7 '18 at 11:58

It would be $O(n^2)$ in the worst case. Suppose root of BST is $15$, all left nodes are $7$, and all right nodes are $21$. We want to find all pairs which their sum is $28$. Hence, you should report all $\frac{n}{2}\times \frac{n}{2}$ items (all left nodes with all right nodes). Hence, your algorithms should report $O(n^2)$ pairs in the worst case.