Find a Pair with the given sum in a BST

By | February 16, 2022
Find a Pair with the given sum in a BST

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:

Author: Vinay Singh

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.