Given two BSTs containing n1 and n2 distinct nodes respectively. Given a value x. The problem is to count all pairs from both the BSTs whose sum is equal to x.
Input : BST 1: 5 / 3 7 / / 2 4 6 8 BST 2: 10 / 6 15 / / 3 8 11 18 x = 16 Output : 3 The pairs are: (5, 11), (6, 10) and (8, 8)
Method 1: For each node value a in BST 1, search the value (x – a) in BST 2. If value found then increment the count. For searching a value in BST, refer this post.
Time complexity: O(n1 * h2), here n1 is number of nodes in first BST and h2 is height of second BST.
Method 2: Traverse BST 1 from smallest value to node to largest. This can be achieved with the help of iterative inorder traversal. Traverse BST 2 from largest value node to smallest. This can be achieved with the help of reverse inorder traversal. Perform these two traversals simultaneously. Sum up the corresponding node’s value from both the BSTs at a particular instance of traversals. If sum == x, then increment count. If x > sum, then move to the inorder successor of the current node of BST 1, else move to the inorder predecessor of the current node of BST 2. Perform these operations until either of the two traversals gets completed.
Pairs = 3
Time Complexity: O(n1 + n2)
Auxiliary Space: O(n1 + n2)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.