Last Updated: 3 Dec, 2020

Pair with Given Sum in a Balanced BST

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The idea is to traverse the tree and keep track of nodes we have visited if for a given node’s ‘value’, we have visited ‘target’ - ‘value’, we return true else we add that value to our hash-map.

The steps are as follows:

Maintain a hash-map ‘mp,’ which keeps track of the nodes we have visited.
We will use a helper function, ‘helper’.
‘helper’ takes ‘root,’ ‘target,’ and ‘mp’ as input parameters, where ‘root’ is the root of the binary tree, ‘target’ is the value which should be equal to sum of 2 nodes and ‘mp’ is the hash-map we use to keep track of nodes visited.
- For a given root ‘toFind’ value is the other half that we need to find to make a pair whose sum is equal to ‘target’, for the given ‘root’s data value.
- If for the current node we have visited a node whose value is ‘toFind’ and they are not the same nodes, we return true.
- Else we recur for the left and right nodes of the current node.
- If we find the pair, we return true. Else we return false as the final answer.

Solve now