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 into the set. If we see that ( sum-current node) exists in the set, we have found the pair. Otherwise, we keep on searching for 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:
- Construction of an Expression Tree
- Create a mirror of an m–ary Tree
- Print a two-dimensional view of a Binary Tree
- Rearrange an array such that arr[i] = i
- Rod Cutting Problem
- Print all subarrays with 0 sum
- Merge Two Sorted Arrays in-place
- Diameter of a Binary Tree
- Bottom View of a Binary Tree
- Reverse a Linked List
