Find a Pair with the given sum in a BST

Posted in

Find a Pair with the given sum in a BST

Vinay Khatri
Last updated on June 8, 2022

    Problem

    Given a binary tree, the task is to find a pair with the given sum. The elements of the tree are pairwise distinct.

    Sample Input

    Sum = 11
    
    

    Sample Output

    Pair is (4, 7)

    Approach

    We will use an unordered set to solve this problem. This is because an unordered set gives the time complexity of O(1) if there are not many duplicates present in it. Since, in the BST, we have all values different, we can use this data structure for the solution. We traverse the tree and keep inserting the elements in the set. If we see that ( sum-current node) exists in the set, we have found the pair. Otherwise, we keep on searching the tree.

    Complexity Analysis

    The time complexity would be O(N) as we are traversing the entire tree. The space complexity would be O(N) due to the call stack and auxiliary data structure.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    struct TreeNode
    {
        int val;
        TreeNode *left, *right;
    };
    
    // create new bode
    TreeNode* newNode(int ele)
    {
        TreeNode* node = new TreeNode;
        node->val = ele;
        node->left = node->right = nullptr;
    
        return node;
    }
    
    // insert new node
    TreeNode* insert(TreeNode* root, int ele)
    {
        // if the root is null
        if (root == nullptr) {
            return newNode(ele);
        }
    
        // if the given ele is less than the root node
        if (ele < root->val) {
            root->left = insert(root->left, ele);
        }
    
        // if the given ele is more than the root node
        else {
            root->right = insert(root->right, ele);
        }
    
        return root;
    }
    
    bool solve(TreeNode* root, int sum, auto &us)
    {
        // base case
        if (root == nullptr) {
            return false;
        }
    
        // return true if pair is found in the left subtree
        if (solve(root->left, sum, us)) {
            return true;
        }
    
        // if the pair found
        if (us.find(sum - root->val) != us.end())
        {
            cout << "Pair is (" << sum - root->val << ", " << root->val << ")";
            return true;
        }
    
        // insert the current node's value into the set
        else {
            us.insert(root->val);
        }
    
        // search in the right subtree
        return solve(root->right, sum, us);
    }
    
    int main()
    {
        int values[] = {1, 3, 4, 6, 7, 8, 10, 13, 14};
    
        TreeNode* root = nullptr;
    
        for (int ele: values) {
            root = insert(root, ele);
        }
    
        int sum = 11;
    
        unordered_set<int> us;
    
        if (!solve(root, sum, us)) {
            cout << "Pair not present";
        }
    
        return 0;
    }

    Output

    Pair is (4, 7)

    Java Programming

    import java.util.HashSet;
    import java.util.Set;
    
    class TreeNode
    {
        int val;
        TreeNode left = null, right = null;
    
        TreeNode(int val) {
            this.val = val;
        }
    }
    
    class Main
    {
        // insert nodes
        public static TreeNode insert(TreeNode root, int ele)
        {
            // if the root is null, create node
            if (root == null) {
                return new TreeNode(ele);
            }
    
            // if the given ele is less than the root node
            if (ele < root.val) {
                root.left = insert(root.left, ele);
            }
    
            // if the given ele is more than the root node
            else {
                root.right = insert(root.right, ele);
            }
            return root;
        }
    
        public static boolean solve(TreeNode root, int sum, Set<Integer> us)
        {
            // base case
            if (root == null) {
                return false;
            }
    
            // return true if pair is found in the left subtree
            if (solve(root.left, sum, us)) {
                return true;
            }
    
            // if a pair is formed with the current node
            if (us.contains(sum - root.val))
            {
                System.out.print("Pair is (" + (sum - root.val) + ", "
                                        + root.val + ")");
                return true;
            }
    
            // insert the current node's value into the set
            else {
                us.add(root.val);
            }
    
            // search in the right subtree
            return solve(root.right, sum, us);
        }
    
        public static void main(String[] args)
        {
            int[] values = {1, 3, 4, 6, 7, 8, 10, 13, 14};
    
            TreeNode root = null;
            for (int ele: values) {
                root = insert(root, ele);
            }
    
            int sum = 11;
    
            // create an empty set
            Set<Integer> us = new HashSet<>();
    
            if (!solve(root, sum, us)) {
                System.out.print("Pair not present");
            }
        }
    }

    Output

    Pair is (4, 7)

    Python Programming

    class TreeNode:
        def __init__(self, val, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    # insert keys into BST
    def insert(root, key):
        # if the root is None, create a new node 
        if root is None:
            return TreeNode(key)
    
        # if the given key is less than the root node
        if key < root.val:
            root.left = insert(root.left, key)
    
        # if the given key is more than the root node
        else:
            root.right = insert(root.right, key)
        return root
    
    def check(root, sum, us):
        # base case
        if root is None:
            return False
    
        # return true if pair is found in the left subtree
        if check(root.left, sum, us):
            return True
    
        # if a pair is formed with the current node
        if sum - root.val in us:
            print("Pair is", (sum - root.val, root.val))
            return True
    
        # insert the current node's value into the set
        else:
            us.add(root.val)
    
        # search in the right subtree
        return check(root.right, sum, us)
    
    keys = [1, 3, 4, 6, 7, 8, 10, 13, 14]
    
    root = None
    
    for key in keys:
        root = insert(root, key)
    
    sum = 11
    
    # create an empty set
    us = set()
    
    if not check(root, sum, us):
        print("Pair not present")

    Output

    Pair is (4, 7)

    Conclusion

    In this tutorial, we have used an unordered set to find a pair with the given sum, i.e., 11, in a binary tree, provided that the elements in the tree are pairwise distinct. We have implemented it in three different languages, namely Python, Java, and C++. Since all the elements in a tree are distinct, using an unordered set gives the time complexity of O(1). If you have any queries regarding the implementation of the above program, feel free to share them in the comments section below. People are also reading:

    Leave a Comment on this Post

    0 Comments