Pair with Given Sum in a Balanced BST

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in companies
SalesforceCultfitMeesho

Problem statement

You are given the ‘root’ of a Balanced Binary Search Tree and an integer ‘target,’ you have to tell if there exists any pair of nodes such that the sum of their value is equal to the target.

More formally check if there exist any two distinct nodes, whose sum is equal to ‘target.’

Note:

A binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

A balanced binary search tree is a tree in which each node has either 0 or 2 children.
Example: 
For Example, the root node is given as follows :
‘ROOT’ = 5 2 6 -1 -1 -1 -1 and ‘target’ = 8, The answer will be true since the sum of both leaf nodes is equal to 8.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’, representing the number of test cases.

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

The second line of each test case contains a single integer ‘target’, which denotes the sum of that pair of nodes.
Output Format : 
For every test case, print a single line that contains a single integer which denotes whether the pair exists or not.

The output of each test case is printed in a separate line.
Note: 
You don’t have to print anything. It has already been taken care of. Just implement the function.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 1000
0 <= data <= 10 ^ 3
0 <= ‘target’ <= 10 ^ 3

Time Limit: 1sec
Sample Input 1:
2
5 2 6 -1 -1 -1 -1 
8
4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1 
6
Sample Output 1:
1
1

Explanation of the Sample Input 1:

For the first test case, The answer will be true since the sum of both leaf nodes, i.e. the roots left node(2) and the roots right node(6) is equal to 8.

For the second test case, The answer will be true, since the sum of the 4th node(1) and 7th node(5) is equal to 6.
Sample Input 2:
2
5 2 7 1 3 6 9 -1 -1 -1 -1 -1 -1 -1 -1
10
5 2 7 1 3 6 9 -1 -1 -1 -1 -1 -1 -1 -1 
20
Sample Output 2:
1
0
Hint

Can we check for each node?

Approaches (2)
Checking For Every Node

The idea is to fix one node and try to find, if there exists, a node whose sum along with the fixed node is equal to the given ‘target’.

 

The steps are as follows:

  • We will use a helper function ‘findTargetPairHelper’ to fix each node.
  • ‘findTargetPairHelper’ takes ‘mainRoot,’ ‘curRoot’ and ‘target’ as input parameters, ‘mainRoot’ is the root of the given tree, ‘curRoot’ is the node we are fixing and ;target; is the given target.
  • To check if ‘curRoot’ has a pair, we use another helper function, ‘helper.’
    • ‘helper’ takes ‘root,’ ‘firstHalf’ and ‘target’ as input parameters, where ‘firstHalf’ is the node we fixed.
    • Then we traverse the tree to find any node such that ‘firstHalf’ data plus nodes data equal to ‘target’.
    • If we find such a node, we return true. Else we return false.
  • If for ‘curRoot’ we find the pair, we return true. Else we return false as the final answer.
Time Complexity

O(N ^ 2), where ‘N’ is the number of nodes in the binary tree.


We are traversing the whole binary for each node. Hence, the overall time complexity is O(N ^ 2). 

Space Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.


We are traversing the whole binary once. Hence, the overall recursive stack made will be equal to the height of the tree. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Pair with Given Sum in a Balanced BST
Full screen
Console