Triple Sum
It was Todd’s Birthday, So Bojack decided to give Todd a Binary tree with ‘N’ nodes. But the binary tree was too big to keep in his house, so Bojack decided to give exactly three nodes from that tree such that the sum of these three numbers equals ‘X’. Can you help Bojack determine if it is possible to make a sum equal to ‘X’?

For Example :

X = 11

The sum of nodes 7, 3, 1 is 11. So we will return True.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases. The first line of each test case contains the elements of the binary tree in the level order form separated by a single space. The second line of the test case contains an integer denoting ‘X’. If any node does not have a left or right child, take -1 in its place. Refer to the example below.

1 2 3 -1 4 -1 -1 5 -1 -1 -1 Explanation : Level 1 : The root node of the tree is 1 Level 2 : Left child of 1 = 2 Right child of 1 = 3 Level 3 : Left child of 2 = null (-1) Right child of 2 = 4 Left child of 3 = null (-1) Right child of 3 = null (-1) Level 4 : Left child of 4 = 5 Right child of 4 = null (-1) Level 5 : Left child of 5 = null (-1) Right child of 5 = null (-1) The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are null (-1). Note: The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 1 2 3 -1 4 -1 -1 5 -1 -1 -1

Output Format :

For each test case, print a boolean True or False. Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints :

1

Question

Triple Sum

It was Todd’s Birthday, So Bojack decided to give Todd a Binary tree with ‘N’ nodes. But the binary tree was too big to keep in his house, so Bojack decided to give exactly three nodes from that tree such that the sum of these three numbers equals ‘X’. Can you help Bojack determine if it is possible to make a sum equal to ‘X’?

For Example :

X = 11

The sum of nodes 7, 3, 1 is 11. So we will return True.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains the elements of the binary tree in the level order form separated by a single space.

The second line of the test case contains an integer denoting ‘X’.

If any node does not have a left or right child, take -1 in its place. Refer to the example below.

1
2 3
-1 4 -1 -1
5 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = null (-1)
Right child of 2 = 4
Left child of 3 = null (-1)
Right child of 3 = null (-1)

Level 4 :
Left child of 4 = 5
Right child of 4 = null (-1)

Level 5 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note: The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 -1 4 -1 -1 5 -1 -1 -1

Output Format :

For each test case, print a boolean True or False.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints :

1 <= T <= 100
1 <= N <= 3000
1 <= NodeVal <= 1000
1 <= X <= 1000

Time Limit: 1sec

Accepted Answer

The task is to determine if it is possible to select three nodes from a binary tree such that their sum equals a given value.

Traverse the binary tree and store all the node values in an array
Use three nested loops to iterate through all possible combinations of three nodes
Check if the sum of the three nodes equals the given value
If a valid combination is found, return True
If no valid combination is found, return False

Accepted Answer

Step1. Implemented brute force solution first.
Step2. Then saw as order of elements does not mattered so thought of sorting it and to use 2 pointer
Step3. Implemented it.

Accepted Answer

Naive Approach

The Approach is simple. We will find the value of every node using dfs and then increase the count of every value. After completing dfs, We will loop through the list and, for a given value, check if there are two other elements present such that the sum of these three numbers is X.

The steps are as follows :

Take a list arr to store the count of elements.
In the ‘dfs’ function:
1. Write the base condition, i.e., if the root is NULL return.
2. If the data of the current node is less than X, then Increment its value in the list by 1.
3. Call ‘dfs’ function for the left and right sides of the node.
In the Main Function:
1. Call the ‘dfs’ function to store the count of every element in the list.
2. Now iterate through the list arr from 1 to X(say iterator be i) :
  1. If the count of arr[ i ] > 0, decrease the count by 1 to avoid retaking the current number.
  2. Iterate through the list arr from i to X(say iterator be j) :
    1. If the count of arr[ j ] > 0, then decrease the count by 1.
    2. Iterate through the list from j to X(say iterator be k) :
      1. If the count of arr[ k ] > 0 and sum of i + j + k is equal to X, then return true.
    3. Increment the value of arr[ j ] again by 1.
  3. Increment the value of arr[ i ] again by 1.
3. Return false if we could not find any such triplets.

Space Complexity: OtherExplanation:

O(X), Where X is the value given in the problem statement

We are using a list arr of size X to store the count of nodes, Hence the space complexity is O(X).

Time Complexity: OtherExplanation:

O(X^3). Where X is the value given in the problem statement.

We are iterating through the list in nested loops from 1 to X, Hence the time complexity is O(X^3).

Python (3.5)

'''
    Time Complexity : O(X^3)
    Space Complexity : O(X)

    Where, X is the required sum.
'''

def dfs(root, m, x):
    
    # If no element is present return.
    if root == None:
        return
    
    # If data of current node is less than x than increase count.
    if root.data <= x:
        m[root.data] += 1
                
    # Traverse in the left tree.
    if root.left != None:
        dfs(root.left, m, x)
        
    # Traverse in the right tree.
    if root.right != None:
        dfs(root.right, m, x)
        
def checkTriplet(root, x):
    
    m = [0 for i in range(x + 1)]
    dfs(root, m, x)
    
    for i in range(x + 1):
        
        if m[i] > 0:
            
            # Decrease the count of current value to avoid retaking the current element.
            m[i] -= 1
            for j in range(i, x + 1):
                
                if m[j] > 0:
                    m[j] -= 1
                    
                    for k in range(j, x + 1):
                        
                        if (m[k] > 0 and i + j + k == x):
                            
                            # If a triplet is present return true.
                            return True
                        
                    m[j] += 1
                    
    return False

C++ (g++ 5.4)

/*

    Time Complexity : O(X^3)

    Space Complexity : O(X)



    Where, X is the required sum.

*/



void dfs(TreeNode *root, vector &m, int x) {



    // If no element is present return.

    if (!root) {

        return;

    }



    // If data of current node is less than x than increase count.

    if (root->data <= x) {

        m[root->data]++;

    }



    // Traverse in the left tree.

    if (root->left) {

        dfs(root->left, m, x);

    }



    // Traverse in the right tree.

    if (root->right) {

        dfs(root->right, m, x);

    }

}



bool checkTriplet(TreeNode *root, int x) {



    // Vector to store the count of nodes.

    vector m(x + 1, 0);



    // Function call.

    dfs(root, m, x);

    for (int i = 0; i <= x; i++) {

        if (m[i]) {



            /*

                Decrease the count of current value

                to avoid retaking the current element.

            */

            m[i]--;

            for (int j = i; j <= x; j++) {

                if (m[j]) {

                    m[j]--;

                    for (int k = j; k <= x; k++) {

                        if (m[k] and i + j + k == x) {



                            // If a triplet is present return true.

                            return true;

                        }

                    }

                    m[j]++;

                }

            }



            // Increase the count.

            m[i]++;

        }

    }

    return false;

}

Java (SE 1.8)

/*

    Time Complexity : O(X^3)

    Space Complexity : O(X)



    Where, X is the required sum.

*/



public class Solution {



    static void dfs(TreeNode root, int[] m, int x) {



        // If no element is present return.

        if (root == null) {

            return;

        }



        // If data of current node is less than x than increase count.

        if (root.data <= x) {

            m[root.data]++;

        }



        // Traverse in the left tree.

        if (root.left != null) {

            dfs(root.left, m, x);

        }



        // Traverse in the right tree.

        if (root.right != null) {

            dfs(root.right, m, x);

        }



    }



    static boolean checkTriplet(TreeNode root, int x) {

        int[] m = new int[x + 1];

        dfs(root, m, x);

        for (int i = 0; i <= x; i++) {

            if (m[i] > 0) {



                // Decrease the count of current value to avoid retaking the current element.

                m[i]--;

                for (int j = i; j <= x; j++) {

                    if (m[j] > 0) {

                        m[j]--;

                        for (int k = j; k <= x; k++) {

                            if (m[k] > 0 && i + j + k == x) {



                                // If a triplet is present return true.

                                return true;

                            }

                        }

                        m[j]++;

                    }

                }



                // Increase the count.

                m[i]++;

            }

        }

        return false;

    }



}

Accepted Answer

Optimal Approach

In this approach, we will find the value of every node using dfs and then increase the count of every value. After completing dfs, We will loop through the list and select a value and then loop through the list to select another value such that there is a third element present in the list having value X - ‘firstElement’ - ‘secondElement’.

The steps are as follows :

Take a list arr to store the count of elements.
In the ‘dfs’ function:
1. Write the base condition, i.e., if the root is NULL return.
2. If the data of the current node is less than X, then Increment its value in the list by 1.
3. Call ‘dfs’ function for the left and right sides of the node.
In the Main Function:
1. Call the ‘dfs’ function to store the count of every element in the list.
2. Now iterate through the list arr from 1 to X(say iterator be i) :
  1. If the count of arr[ i ] > 0, then decrease the count by 1 to avoid retaking the current number.
  2. Iterate through the list arr from i to X(say iterator be j) :
    1. If the count of arr[ j ] > 0, then decrease the count by 1.
    2. Check if there is a third element present in the list having value ‘X - (arr[ i ] + arr[ j ])’.
    3. Return true if any such value is present in the list.
    4. Increment the value of arr[ j ] again by 1.
  3. Increment the value of arr[ i ] again by 1.
3. Return false if we could not find any such triplets.

Space Complexity: OtherExplanation:

O(X), Where X is the value given in the problem statement

We are using a list arr of size X to store the count of nodes, Hence the space complexity is O(X).

Time Complexity: OtherExplanation:

O(X^2). Where X is the value given in the problem statement.

We are iterating through the list in nested loops from 1 to X, Hence the time complexity is O(X^2).