2 sum binary tree

Question:

In this question, we have to solve the “2 Sum Binary Tree” problem, which aims to determine if there are two nodes in a binary tree whose values sum up to a target value or not.

If we found the targeted value in the binary tree, we will return “Found” as an output. Else, we will return “Not Found” as an output.

Code:

#include <iostream>
#include <unordered_set>

using namespace std;

// Define binary tree node
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

// this function will help us to check if a target sum can be found using two nodes in the binary tree or not
bool findTarget(TreeNode* root, int k, unordered_set<int>& nums) {
    if (root == nullptr)
        return false;

    if (nums.count(k - root->value) > 0)
        return true;

    nums.insert(root->value);

    return findTarget(root->left, k, nums) || findTarget(root->right, k, nums);
}

// this function will check if a target sum can be found using two nodes in the binary tree or not
bool finalFindTarget(TreeNode* root, int k) {
    unordered_set<int> nums;
    return findTarget(root, k, nums);
}

int main() {
    // Creating a binary tree manually
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);

    int targetNum = 9;

    // Checking if a target sum can be found using two nodes in the binary tree or not
    bool result = finalFindTarget(root, targetNum);

    cout << "Target sum " << targetNum << " can " << (result ? "be" : "not be") << " found using two nodes in the binary tree." << endl;

    return 0;
}

Explanation of the above code:

Here’s a step-by-step explanation of how actually the 2 sum binary tree code works:

1. So, in the above code, we will first define the binary tree node struct, TreeNode, which represents a node in the binary tree. And here, each node contains a value (value variable) and pointers to its left and right children as left and right variables.
2. Now, we will make a findTarget function, which is a recursive helper function that takes a node (root), a target value (k), and a set of visited numbers (nums) as a parameter. In this function, we will checks if a target sum can be achieved using two nodes in the binary tree or not.
3. So, In the above function, 
   • If the root is nullptr, it indicates that it is an empty node and it will return false.
   • After that, it checks if the complement of the current node’s value (k – root->value) exists in the nums set or not.
   • If it does, it means a pair of nodes with the desired sum is found, and it will return true.
   • Otherwise, it inserts the current node’s value (root->value) into the nums set for future reference.
4. After this, it will recursively call itself a return value. And this function will return true if either of the recursive calls returns true.  This indicates that a pair of nodes with the target sum is found either in the left subtree or right subtree.
5. After this, we will make a finalFindTarget function that initializes an empty num set and calls the findTarget function with the root of the binary tree and the target value k.
6. In the main function:
   • Firstly, a binary tree is manually created by creating TreeNode objects and linking them together one by one. Here, we declare the target sum as 9.
   • Then, the finalFindTarget function is called with the root of the binary tree and the target sum.
   • Finally, the result is printed, indicating whether a pair of nodes with the target sum exists in the binary tree.
7. In the above code, the binary tree contains nodes with values 2, 3, 4, 5, 6, and 7. The sum of nodes 2 and 7 equals the target value of 9. Therefore, the output states that the target sum of 9 can be found using two nodes in the binary tree.

Find a pair with the given sum in a Balanced BST :

if you also want to find a pair value that is equal to the target value, then you can refer to the below code.

#include <iostream>
#include <unordered_set>

using namespace std;

// Define binary tree node
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

// Function to check if a pair value equal to the target exists in the binary tree or not
bool findPair(TreeNode* root, int target, unordered_set<int>& nums, int& node1, int& node2) {
    if (root == nullptr)
        return false;

    if (nums.count(root->value) > 0) {
        node1 = target - root->value;
        node2 = root->value;
        return true;
    }

    nums.insert(target - root->value);

    return findPair(root->left, target, nums, node1, node2) || findPair(root->right, target, nums, node1, node2);
}

int main() {
    // Creating a binary tree manually
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);

    int target = 9;
    int node1, node2;

    // Checking if a pair value equal to the target exists in the binary tree
    unordered_set<int> nums;
    bool result = findPair(root, target, nums, node1, node2);

    if (result) {
        cout << "Pair values equal to " << target << " found in the binary tree: " << node1 << " and " << node2 << endl;
    } else {
        cout << "No pair values equal to " << target << " found in the binary tree." << endl;
    }

    return 0;
}

Explanation of the above code:

The solution will be the same but we just have to take two new variables node1 and node2 to store the value that is equal to the target value.
So, for that:

1. We have to make a “findPair” function which is a recursive function that searches for a pair of values in a binary tree that is equal to the target value.
2. So, the findPair function takes the following parameters:
   • root: It is a TreeNode pointer
   • target: The target value
   • nums: A reference to an unordered set that stores the uncovered values.
   • node1 and node2: References to two integer variables to store the pair values if the targeted value will be founded.
3. If the current node is equal to nullptr, it means we have reached a leaf node or an empty subtree, so the function returns false to indicate that no pair was found.
4. If the current node’s value is present in the “num” set that means a pair exists in the tree. In that case, the function calculates the second value of the pair by subtracting the current node’s value from the target value (node1 = target – root->value). It also assigns the current node’s value to node2. Then, it returns true to indicate that a pair was found.
5. If the current node’s value is not found in the nums set, it means the complement value needed for a pair is not encountered yet. So, it inserts the complement of the current node’s value (target – root->value) into the nums set again. So, the function traverses the tree again to keep track of all the complement values.
6. Then, the function makes two recursive calls, one for the left subtree and one for the right subtree. It passes the left child and right child nodes, respectively, along with the remaining parameters.
7. If no pair is found in the current subtree or its children, the function returns false to indicate that no pair was found.

Overall, the findPair function recursively traverses the binary tree, using an unordered set to track values encountered, and returns true if a pair of values, adding up to the target is found, and false, if there is no pair found.

Conclusion

Overall, this blog provides a clear explanation of the problem “2 sum binary tree” and presents a solution using a recursive approach with an unordered set, and also provides a code example for implementation. As well as it also offers valuable understanding into solving the 2-sum problem in a binary tree efficiently with two different approaches.