Pair Sum in BST.
You are given a Binary Search Tree (BST) and a target value ‘K’. Your task is to check if there exist two unique elements in the given BST such that their sum is equal to the given target ‘K’.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data. • The right subtree of a node contains only nodes with data greater than the node’s data. • Both the left and right subtrees must also be binary search trees.

Note:

1. All the elements of the Binary Search Tree are unique. 2. You can’t use the same node value/element of BST twice.

Input Format:

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows. The first line of every test case contains elements of Binary Search Tree in the level order form. The input consists of values of nodes separated by a single space in a single line. In case, a node is null, we take -1 in its place. The second line of every test case contains a single integer ‘K’ which denotes the target value.

For example:

The input for the tree depicted in the below image would be :

20 10 35 5 15 30 42 -1 13 -1 -1 -1 -1 -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 = 4 Right child of 2 = null (-1) Left child of 3 = 5 Right child of 3 = 6 Level 4 : Left child of 4 = null (-1) Right child of 4 = 7 Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 6 = null (-1) Right child of 6 = null (-1) Level 5 : Left child of 7 = null (-1) Right child of 7 = 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 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, print a single line containing “true” or “false”.

Note:

You don’t need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Pair Sum in BST.

You are given a Binary Search Tree (BST) and a target value ‘K’. Your task is to check if there exist two unique elements in the given BST such that their sum is equal to the given target ‘K’.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Note:

1. All the elements of the Binary Search Tree are unique.
2. You can’t use the same node value/element of BST twice.

Input Format:

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case  follows. 

The first line of every test case contains elements of Binary Search Tree in the level order form. The input consists of values of nodes separated by a single space in a single line. In case, a node is null, we take -1 in its place.

The second line of every test case contains a single integer ‘K’ which denotes the target value.

For example:

The input for the tree depicted in the below image would be :

20 10 35 5 15 30 42 -1 13 -1 -1 -1 -1 -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 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

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

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = 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 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, print a single line containing “true” or “false”.

Note:

You don’t need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5    
1 <= N <= 10 ^ 3
0 <= DATA <= 10 ^ 9
1 <= K <= 10 ^ 9 

Where ‘DATA’ denotes the value of each node in the given tree and ‘N’ denotes the number of nodes in BST.

Time limit: 1 sec

Accepted Answer

The task is to check if there exist two unique elements in the given BST such that their sum is equal to the given target 'K'.

Traverse the BST in-order and store the elements in a sorted array
Use two pointers, one at the beginning and one at the end of the array
Check if the sum of the elements at the two pointers is equal to the target 'K'
If the sum is less than 'K', move the left pointer to the right
If the sum is greater than 'K', move the right pointer to the left
Repeat the above steps until the pointers meet or the sum is found

Accepted Answer

Step 1 : Earlier, this question seems to be very easy, I told the approach using O(n) TC and O(n) SC, then interviewer asked me to optimise the SC.

Step 2 : I told the another approach using O(n(logn)) TC and O(1) SC, but again interviewer was not happy and this time she asked me to optimise TC.

Step 3 : After lot of thinking, I cam up with the solution using Stack DS, that takes O(n) TC and O(heigh_of_tree) SC, this was the approach interviewer was looking for, he asked me to write the code

Accepted Answer

Brute Force Approach

The idea is that if the sum of any two elements say, ‘A’ and ‘B’ is equal to the given value ‘K’, and we already know that ‘A’ is present in the given tree then we only need to check whether element ‘B’ = ‘K’ - ‘A’ exists in the tree or not. We can check this by using the property of the binary search tree.

Approach :

Using depth-first search (DFS), we traverse the given BST.
For each node, we calculate the value ‘Q’ i.e ‘K’ - current node’s value.
Now, using the property of BST, we search this value in the given tree.
- If the value of the current node is less than ‘Q’, we will search in the right subtree recursively.
- If the value of the current node is more than ‘Q’, we will search in the left subtree recursively.
- If the value of the current node equals ‘Q’, we will return “true” to the function.
- If the value is not found for any node, we will return “false” to the function.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the given BST (Binary Search Tree).

O(H) recursion stack space is used by the algorithm where H is the height of BST. In the worst case (for skewed trees), H will become N. Hence, the overall space complexity will be O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of nodes in the given BST (Binary Search Tree).

Since, we will be traversing each node of BST with O(N), and for each node, we will be searching in a given BST which takes O(H) time. For skewed trees, H will become N.Hence, the overall time complexity will be O(N ^ 2).

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of nodes in the BST.

*/



// Function to search the difference of current node's value and target 'k'. 

bool search(BinaryTreeNode *root, BinaryTreeNode *cur, int diff)

{

    if (root == NULL)

    {

        return false;

    }



    if (root -> data < diff)

    {

        return search(root -> right, cur, diff);

    }



    if (root -> data > diff)

    {

        return search(root -> left, cur, diff);

    }



    // This means that we have found the node having value equal to the diff.

    if (cur != root)

    {

        return true;

    }



    return false;

}



bool dfs(BinaryTreeNode *root, int k, BinaryTreeNode *cur)

{

    if (cur == NULL)

    {

        return false;

    }



    // Visit each node of BST and call the 'search' function.

    return (search(root, cur, k - cur->data) || dfs(root, k, cur -> left) || dfs(root, k, cur -> right));

}



bool pairSumBst(BinaryTreeNode *root, int k)

{

    return dfs(root, k, root);

}

Java (SE 1.8)

/*
    Time Complexity: O(N ^ 2)
    Space Complexity: O(N)
    
    Where 'N' denotes the number of nodes in the BST.
*/

public class Solution {

	// Function to search the difference of current node's value and target 'k'.
	public static boolean search(BinaryTreeNode root, BinaryTreeNode cur, int diff) {
		if (root == null) {
			return false;
		}

		if (root.data < diff) {
			return search(root.right, cur, diff);
		}

		if (root.data > diff) {
			return search(root.left, cur, diff);
		}

		// This means that we have found the node having value equal to the diff.
		if (cur != root) {
			return true;
		}

		return false;
	}

	public static boolean dfs(BinaryTreeNode root, int k, BinaryTreeNode cur) {
		if (cur == null) {
			return false;
		}

		// Visit each node of BST and call the 'search' function.
		return (search(root, cur, k - cur.data) || dfs(root, k, cur.left) || dfs(root, k, cur.right));
	}

	public static boolean pairSumBst(BinaryTreeNode root, int k) {
		return dfs(root, k, root);
	}
}

Python (3.5)

''' 

    Time Complexity: O(N ^ 2)

    Space Complexity: O(N)

    

    Where N is the number of nodes in the given BST.

'''



# Function to search the difference of current node's value and target 'k'. 

def search(root, cur, value):

    if root == None:

        return False



    if root.data < value:

        return search(root.right, cur, value)



    if root.data > value:

        return search(root.left, cur, value)



    # This means that we have found the node having value equal to the diff.

    if cur != root:

        return True



    return False





def dfs(root, k, cur):

    if cur == None:

        return False



    # Visit each node of BST and call the search function

    return search(root, cur, k - cur.data) or dfs(root, k, cur.left) or dfs(root, k, cur.right)





def pairSumBST(root, k):

    

    return dfs(root, k, root)

Accepted Answer

Inorder Traversal

In this approach, we use the property of the inorder traversal of BST. The inorder traversal of a BST always traverses the nodes of BST in the increasing order of their values.

Thus, we do the inorder traversal of the given tree and we store all the values of the nodes in an array. This will give us an array in increasing order. Now we can use the two-pointer technique on this sorted list for determining if two elements exist in the list which sums up to the target value ‘K’.

Approach :

First create an array say, ‘NUMS’.
Create a recursive function, say ‘inorder ( ROOT, NUMS)’ passing ‘ROOT’ and ‘NUMS’ in its arguments.
Now call the recursive function ‘inorder ( ROOT, NUMS)’, to store the inorder traversal of a given tree in the array, ‘NUMS’
Use the two-pointer technique in the array, ‘NUMS’.
Set iterator pointer ‘i’ at the start, and iterator pointer ‘j’ at the end of the array ‘NUMS’
If the sum of the values at index ‘i’ and index ‘j’ is greater than the target ‘K’, decrement ‘j’ by 1.
If the sum of the values at index ‘i’ and index ‘j’ is less than the target ‘K’, increment ‘i’ by 1.
If the sum of the values at index ‘i’ and index ‘j’ is equal to the target ‘K’, then return “true” to the function.
At last, we return “false” to the function, if we didn't find any two elements with sum = ‘K’.

Description of ‘inorder’ function

This function will take two parameters :

‘ROOT’ that is the root of the given BST.
‘NUMS’ array which we have defined above.

void inorder(ROOT, NUMS):

Until all the nodes are traversed
Recursively traverse the left subtree.
Add the current node’s value to the ‘NUMS’.
Recursively traverse the right subtree.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in a given BST(Binary Search Tree).

In the worst case, we are storing each node of BST in the array ‘NUMS’, and extra space is required for the recursion stack. Hence, overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in a given BST(Binary Search Tree).

In the worst case, we will be traversing each node of BST with O(N), and traversing the array ‘NUMS’ which will take O(N) time. Hence, the overall time complexity will be O(N).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of nodes in the given BST

*/



// Function to store inorder traversal of BST in 'nums'.

void inorder(BinaryTreeNode *root, vector &nums)

{

    if (root == NULL)

    {

        return;

    }



    inorder(root -> left, nums);



    nums.push_back(root -> data);



    inorder(root -> right, nums);

}





bool pairSumBst(BinaryTreeNode *root, int k)

{

    // Vector to store the inorder traversal of the BST.

    vector nums;



    inorder(root, nums);



    // Iterating over the nums list using 2 - pointer.

    int i = 0, j = nums.size() - 1;



    // Iterate till 'i' is less than 'j'.

    while (i < j)

    {

        if (nums[i] + nums[j] == k)

        {

            return true;

        }



        // If the sum of elements at index 'i' and 'j' is less than target 'k'.  

        if (nums[i] + nums[j] < k)

        {



            // Increment the left pointer 'i'.

            i = i + 1;

        }



        // If the sum of elements at index 'i' and 'j' is greater than target 'k'. 

        else

        {



            // Decrement the right pointer 'j'.

            j = j - 1;

        }

    }



    return false;

}

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)
    
    Where 'N' denotes the number of nodes in the given BST.
*/

import java.util.ArrayList;

public class Solution {
	
	// Function to store inorder traversal of BST in 'nums'.
	public static void inorder(BinaryTreeNode root, ArrayList nums) {
		if (root == null) {
			return;
		}

		inorder(root.left, nums);

		nums.add(root.data);

		inorder(root.right, nums);
	}

	public static boolean pairSumBst(BinaryTreeNode root, int k) {

		// Vector to store the inorder traversal of the BST.
		ArrayList nums = new ArrayList<>();

		inorder(root, nums);

		// Iterating over the nums list using 2 - pointer.
		int i = 0, j = nums.size() - 1;

		// Iterate till 'i' is less than 'j'.
		while (i < j) {
			if (nums.get(i) + nums.get(j) == k) {
				return true;
			}

			// If the sum of elements at index 'i' and 'j' is less than target 'k'.
			if (nums.get(i) + nums.get(j) < k) {

				// Increment the left pointer 'i'.
				i = i + 1;
			}

			// If the sum of elements at index 'i' and 'j' is greater than target 'k'.
			else {

				// Decrement the right pointer 'j'.
				j = j - 1;
			}
		}

		return false;
	}
}

Python (3.5)

''' 

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where N is the number of nodes in the given BST.

'''



# Function to store inorder traversal of BST in 'nums'.

def inorder(root, nums):

    if root == None:

        return



    inorder(root.left, nums)



    nums.append(root.data)



    inorder(root.right, nums)





def pairSumBST(root, k):

    

    # To store the inorder traversal

    nums = []



    inorder(root, nums)



    # Iterating over the nums list using 2-pointer

    i, j = 0, len(nums) - 1

    

    while i < j:

  

        if nums[i] + nums[j] == k:

            return True



        # If the sum of elements at index 'i' and 'j' is less than target 'k'.

        if nums[i] + nums[j] < k:

            # Increment the left pointer 'i'.

            i += 1



        # If the sum of elements at index 'i' and 'j' is greater than target 'k'. 

        else:

            # Decrement the right pointer 'j'.

            j -= 1



    return False

Accepted Answer

Using Set

Instead of searching a second value for every node of the given BST, we can optimise our search by using a set to keep track of elements.

We will traverse the tree in a depth-first-search manner.
For every node, we check if there is a value present in the set which is equal to the difference of given target ‘K’ and the node’s value.
If so, we can say that there are two nodes whose values of the sum are equal to target ‘K’. So, we return “true” to the function.
Else, we will insert the value in the set.

Approach :

Create an empty unordered set, say ‘HASHSET’.
We create a recursive function that traverses each node in the given tree to check the pair sum:
- If ‘ROOT’ is NULL then return “false”.
- If the ‘HASHSET’ contains the ‘K’ - ROOT’s DATA then return “true”.
- Else add ROOT’s DATA into ‘HASHSET’.
- If any of the subtrees either left or right return “true” then return “true” to the function.
- Else return “false” to the function.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in a given BST(Binary Search Tree).

In the worst case, we are storing each node’s value of BST in the set, and extra space is required for the recursion stack. Hence, the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in a given BST (Binary Search Tree).

In the worst case, we will be traversing each node of BST O(N). Hence, the overall time complexity will be O(N).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of nodes in the given BST

*/



#include



bool helper(BinaryTreeNode *root, int k, unordered_set &hashSet)

{

    if (root == NULL)

    {

        return false;

    }



    // If the pair is found then return "true".

    if (hashSet.count(k - root->data))

    {

        return true;

    }



    // If the pair is not found then simply insert the root's data into the 'hashSet'.

    hashSet.insert(root -> data);



    // Recursively check for both left and right subtrees.

    return (helper(root -> left, k, hashSet) || helper(root -> right, k, hashSet));

}





bool pairSumBst(BinaryTreeNode *root, int k)

{

    

    // Set to store the nodes.

    unordered_set hashSet;

    

    return helper(root, k, hashSet);

}

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of nodes in the given BST.

*/



import java.util.HashSet;



public class Solution {

	public static boolean helper(BinaryTreeNode root, int k, HashSet hashSet) {

		if (root == null) {

			return false;

		}



		// If the pair is found then return "true".

		if (hashSet.contains(k - root.data)) {

			return true;

		}



		// If the pair is not found then simply insert the root's data into the

		// 'hashSet'.

		hashSet.add(root.data);



		// Recursively check for both left and right subtrees.

		return (helper(root.left, k, hashSet) || helper(root.right, k, hashSet));

	}



	public static boolean pairSumBst(BinaryTreeNode root, int k) {



		// Set to store the nodes.

		HashSet hashSet = new HashSet<>();



		return helper(root, k, hashSet);

	}

}

Python (3.5)

''' 

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where N is the number of nodes in the given BST.

'''





def pairSumBSTHelper(root, k, hashSet):

    if root == None:

        return False



    # Pair found.

    if k - root.data in hashSet:

        return True



    # If the pair is not found then simply insert the root's data into the 'hashSet'.

    hashSet.add(root.data)



    # Recursively call on both left and right subtrees.

    return pairSumBSTHelper(root.left, k, hashSet) or pairSumBSTHelper(root.right, k, hashSet)





def pairSumBST(root, k):



    # Set to store the nodes.

    hashSet = set()



    return pairSumBSTHelper(root, k, hashSet)

Accepted Answer

Two pointer technique

In this approach, we will maintain a ‘FRONT’ and a ‘BACK’ iterator pointers that will iterate the BST in the order of in-order and reverse in-order traversal respectively.

Approach :

We maintain two stacks, one for storing the leftmost value of the BST, say ‘START’, and another for storing the rightmost value of BST, say ‘END’.
Now, using the two-pointer technique, we check if the sum of values at the top of stack ‘START’ and ‘END’ is equal to the given target ‘K’.
- If they are equal to the target ‘K’, then return “true” to the function.
- If the sum is less than the target ‘K’, we make the ‘FRONT’ iterator point to the next element using the first stack ‘START’.
- Else if the sum is greater than the target ‘K’, we make the ‘BACK’ iterator point to the previous element using the second stack ‘END’.
- At last, if we find no such two elements having sum equal to target ‘K’, then we will return “false” to the function.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the number of nodes in the given BST(Binary Search Tree).

Since, we are using two extra stacks in the algorithm and all the nodes are being pushed into the stacks. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the number of nodes in the given BST(Binary Search Tree).

In the worst case, we will be traversing each node of BST O(N). Hence, the overall time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of nodes in the given BST.

*/



import java.util.Stack;



public class Solution {

	public static boolean pairSumBst(BinaryTreeNode root, int k) {



		/*

	        Stack 'start' and 'end' to store the smaller and larger 

	        values of BST respectively.

    	*/

		Stack start = new Stack<>();

		Stack end = new Stack<>();



		BinaryTreeNode currNode = root;



		// Storing left values of BST in 'start'.

		while (currNode != null) {

			start.push(currNode);

			currNode = currNode . left;

		}



		// Setting currNode again pointing to root.

		currNode = root;



		// Storing right values of BST in 'end'.

		while (currNode != null) {

			end.push(currNode);

			currNode = currNode . right;

		}



		while (start.peek() != end.peek()) {



			// Storing top node's value of 'start' stack in 'val1'.

			int val1 = start.peek().data;



			// Storing top node's value of 'end' stack in 'val2'.

			int val2 = end.peek().data;



			// If sum of 'val1' and 'val2' is equal to 'k' then return "true".

			if (val1 + val2 == k) {

				return true;

			}



			// Move to the next greatest closer value.

			if (val1 + val2 < k) {

				currNode = start.peek().right;

				start.pop();



				while (currNode != null) {

					start.push(currNode);

					currNode = currNode.left;

				}

			}



			// Move to the next smallest closer value.

			else {

				currNode = end.peek().left;

				end.pop();



				while (currNode != null) {

					end.push(currNode);

					currNode = currNode.right;

				}

			}

		}



		// If no two nodes is found, return false.

		return false;

	}

}

Python (3.5)

''' 

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where N is the number of nodes in the given BST.

'''



from collections import deque



def pairSumBST(root, k):

    

    # Deque used as stack.

    '''

        Stack 'start' and 'end' to store the smaller and larger 

        values of BST respectively.

    '''

    start = deque()

    end = deque()



    currNode = root

    

    # Storing left values of BST in 'start'.

    while currNode != None:

        start.append(currNode)

        currNode = currNode.left



    # Setting currNode again pointing to root.

    currNode = root

    

    # Storing right values of BST in 'end'.

    while currNode != None:

        end.append(currNode)

        currNode = currNode.right



    

    while start[-1] != end[-1]:

        # Storing top node's value of 'start' stack in 'val1'.

        val1 = start[-1].data

        # Storing top node's value of 'end' stack in 'val2'.

        val2 = end[-1].data



        # If sum of 'val1' and 'val2' is equal to 'k' then return "true".

        if val1 + val2 == k:

            return True



        # Move to the next greatest closer value.

        if val1 + val2 < k:

            currNode = start[-1].right

            start.pop()

            

            while currNode != None:

                start.append(currNode)

                currNode = currNode.left



        # Move to the next smallest closer value.

        else:

            currNode = end[-1].left

            end.pop()



            while currNode != None:

                end.append(currNode)

                currNode = currNode.right



    # If no two nodes are found, return false.

    return False

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of nodes in the given BST

*/



#include



bool pairSumBst(BinaryTreeNode *root, int k)

{

    

    /*

        Stack 'start' and 'end' to store the smaller and larger 

        values of BST respectively.

    */

    stack*> start, end;



    BinaryTreeNode *currNode = root;

    

    // Storing left values of BST in 'start'.

    while (currNode != NULL)

    {

        start.push(currNode);

        currNode = currNode -> left;

    }



    // Setting currNode again pointing to root.

    currNode = root;

    

    // Storing right values of BST in 'end'.

    while (currNode != NULL)

    {

        end.push(currNode);

        currNode = currNode -> right;

    }



    while (start.top() != end.top())

    {

        

        // Storing top node's value of 'start' stack in 'val1'.

        int val1 = start.top() -> data;

        

        // Storing top node's value of 'end' stack in 'val2'.

        int val2 = end.top() -> data;



        // If sum of 'val1' and 'val2' is equal to 'k' then return "true".

        if (val1 + val2 == k)

        {

            return true;

        }



        // Move to the next greatest closer value.

        if (val1 + val2 < k)

        {

            currNode = start.top() -> right;

            start.pop();

            

            while (currNode != NULL)

            {

                start.push(currNode);

                currNode = currNode -> left;

            }

        }



        // Move to the next smallest closer value.

        else

        {

            currNode = end.top() -> left;

            end.pop();



            while (currNode != NULL)

            {

                end.push(currNode);

                currNode = currNode -> right;

            }

        }

    }



    // If no two nodes is found, return false.

    return false;

}

You are given a Binary Search Tree (BST) and a target value ‘K’. Your task is to check if there exist two unique elements in the given BST such that their sum is equal to the given target ‘K’.

A binary search tree (BST) is a binary tree data structure which has the following properties.

Note:

Input Format:

For example:

Explanation :

Note:

Output Format:

Note:

Constraints:

Top Josh Technology Group Software Developer interview questions & answers

Popular interview questions of Software Developer