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 &gt; 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 &gt; 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.
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.