1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Sorry I forgot to mention that this BST does not accept duplicates. Have added that to the question $\endgroup$ – Ashwin Feb 5 '18 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.