BSTTWOSUM - Editorial

editorial
1

Prerequisites :- Binary Search Trees, BT traversals, HashSet/unordered_set.

Problem :- Given a binary search tree and an integer S, check if there exist two elements in the BST such that their sum is equal to S.

Solution Approach :- We can use Depth-First Search (DFS) approach to traverse the given BST while maintaining a HashSet/unordered_set to store the visited nodes. It checks whether there exist two elements in the BST such that their sum is equal to the given integer S.

Algorithm:

    1. Implement a DFS function that traverses the BST and checks for the existence of a pair with a given sum using an unordered_set.
    1. In the DFS function:
    • If the current node is null, return false.
    • If the complement of the current node’s value (i.e., S - current node’s value) exists in the HashSet, return true.
    • Otherwise, insert the current node’s value into the HashSet.
    • Recursively call the DFS function on the left and right subtrees.
    1. Initialize an empty HashSet and call the DFS function with the root of the BST.
    1. If the DFS function returns true, print “YES”; otherwise, print “NO”.

Time Complexity: O(N), because in the worst case, the algorithm visits all the nodes in the given BST.

Space complexity: O(N), as extra space is needed (unordered_set) to keep track of nodes’ values.