Find two nodes in the BST whose product equals to the target value
Given a binary search tree (BST) and a target value, find two nodes in the BST such that their product equals the given target value. Return an empty array if no such pair exists.
Examples:
Input:
5
/ \
3 8
/ \ / \
2 4 6 10
Output: 3 8
Explanation: 8 * 3 = 24Input:
4
/ \
2 5
/ \ \
1 3 6Output: 5 2
Explanation : 5*2 = 10
Approach1:
This approach to solve the problem is to do inorder traversal of the given BST and store it in an array. Now, use Two Pointer technique to get pairs whose products is equal to given target value. If no pair is found, return an empty vector.
Algorithm:
- Define a struct TreeNode for the nodes in a binary tree.
- Define a class Solution with the following methods:
- An inorder traversal function that takes a TreeNode pointer and a vector<int> reference as inputs. The function traverses the left subtree, stores the value of the current node in the vector, and traverses the right subtree.
- A findTarget function that takes a TreeNode pointer and an integer target as inputs and returns a vector<int>. The function first calls the inorder traversal function to obtain an inorder traversal of the binary search tree. It then initializes two indices l and r to the beginning and end of the inorder traversal vector, respectively. While l < r, the function calculates the product of the values at indices l and r, compares it with the target, and adjusts l and r accordingly. If the product equals the target, it adds the values at indices l and r to the result vector and breaks the loop. Finally, it returns the result vector.
- In the main function:
- Create a binary search tree according to the input specification.
- Initialize an integer target according to the input specification.
- Create an instance of the Solution class.
- Call the findTarget function with the root of the binary search tree and the target as inputs.
- Print the output according to the size of the returned vector.
Below is the implementation of the approach:
C++
// C++ Implementation #include <iostream> #include <stack> #include <vector> using namespace std; // Definition for a binary tree node. struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode( int x) : val(x) , left(NULL) , right(NULL) { } }; class Solution { public : // inorder traversal void inorder(TreeNode* root, vector< int > &in) { if (root == NULL) return ; inorder(root->left, in); // push node value in the vector in.push_back(root->val); inorder(root->right, in); } // function to find two nodes in the BST whose // product equals to the target value vector< int > findTarget(TreeNode* root, int k) { // To store the inorder traversal // and result vector< int > in, res; inorder(root, in); // size of inorder traversal storage // vector int n = in.size(); int l = 0, r = n - 1; // traverse the array inorder // using two pointer l and r while (l < r){ int prod = in[l] * in[r]; // if product of element // at the two pinters is k // return this as res if ( prod == k ){ res.push_back(in[l]); res.push_back(in[r]); break ; } // if prod is less then // increase l as we have to // increase element value else if ( prod < k ) l++; // if prod is greater then // decrease r as we have to // decrease element value else r--; } return res; } }; // Driver code int main() { // Create the BST from Example 1 TreeNode* root = new TreeNode(5); root->left = new TreeNode(3); root->right = new TreeNode(8); root->left->left = new TreeNode(2); root->left->right = new TreeNode(4); root->right->left = new TreeNode(6); root->right->right = new TreeNode(10); int target = 24; Solution s; // Function call vector< int > res = s.findTarget(root, target); // Print the result if (res.size() == 2) cout << res[0] << " " << res[1] << endl; else cout << "No such pair exists in the BST." << endl; return 0; } |
Java
// Java program for the above approach import java.util.ArrayList; import java.util.List; // Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right; TreeNode( int x) { val = x; } } class Solution { // Inorder traversal void inorder(TreeNode root, List<Integer> in) { if (root == null ) return ; inorder(root.left, in); // Push node value in the list in.add(root.val); inorder(root.right, in); } // Function to find two nodes in the BST whose // product equals the target value List<Integer> findTarget(TreeNode root, int k) { // To store the inorder traversal // and result List<Integer> in = new ArrayList<>(); List<Integer> res = new ArrayList<>(); inorder(root, in); // Size of inorder traversal storage // list int n = in.size(); int l = 0 , r = n - 1 ; // Traverse the list inorder // using two pointers l and r while (l < r) { int prod = in.get(l) * in.get(r); // If the product of elements // at the two pointers is k, // add them to the result list if (prod == k) { res.add(in.get(l)); res.add(in.get(r)); break ; } // If prod is less than k, // increase l as we have to // increase element value else if (prod < k) l++; // If prod is greater than k, // decrease r as we have to // decrease element value else r--; } return res; } } // Driver code public class GFG { public static void main(String[] args) { // Create the BST from Example 1 TreeNode root = new TreeNode( 5 ); root.left = new TreeNode( 3 ); root.right = new TreeNode( 8 ); root.left.left = new TreeNode( 2 ); root.left.right = new TreeNode( 4 ); root.right.left = new TreeNode( 6 ); root.right.right = new TreeNode( 10 ); int target = 24 ; Solution s = new Solution(); // Function call List<Integer> res = s.findTarget(root, target); // Print the result if (res.size() == 2 ) System.out.println(res.get( 0 ) + " " + res.get( 1 )); else System.out.println( "No such pair exists in the BST." ); } } // This code is contributed by Susobhan Akhuli |
Python3
# Python Implementation class TreeNode: def __init__( self , x): self .val = x self .left = None self .right = None class Solution: # Inorder traversal def inorder( self , root, in_order): if root is None : return self .inorder(root.left, in_order) # Push node value in the list in_order.append(root.val) self .inorder(root.right, in_order) # Function to find two nodes in the BST whose # product equals the target value def findTarget( self , root, k): # To store the inorder traversal and result in_order, res = [], [] self .inorder(root, in_order) # Size of inorder traversal storage list n = len (in_order) l, r = 0 , n - 1 # Traverse the list in order using two pointers l and r while l < r: prod = in_order[l] * in_order[r] # If the product of elements at the two pointers is k # append them to the result list if prod = = k: res.extend([in_order[l], in_order[r]]) break # If the product is less than k, increase l elif prod < k: l + = 1 # If the product is greater than k, decrease r else : r - = 1 return res # Driver code if __name__ = = "__main__" : # Create the BST from Example 1 root = TreeNode( 5 ) root.left = TreeNode( 3 ) root.right = TreeNode( 8 ) root.left.left = TreeNode( 2 ) root.left.right = TreeNode( 4 ) root.right.left = TreeNode( 6 ) root.right.right = TreeNode( 10 ) target = 24 s = Solution() # Function call result = s.findTarget(root, target) # Print the result if len (result) = = 2 : print (result[ 0 ], result[ 1 ]) else : print ( "No such pair exists in the BST." ) # This code is contributed by Susobhan Akhuli |
C#
// C# program for the above approach using System; using System.Collections.Generic; // Definition for a binary tree node. public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode( int x) { val = x; left = null ; right = null ; } } public class Solution { // Inorder traversal private void Inorder(TreeNode root, List< int > inOrder) { if (root == null ) return ; Inorder(root.left, inOrder); // Push node value in the list inOrder.Add(root.val); Inorder(root.right, inOrder); } // Function to find two nodes in the BST whose // product equals to the target value public List< int > FindTarget(TreeNode root, int k) { // To store the inorder traversal and result List< int > inOrder = new List< int >(); List< int > res = new List< int >(); Inorder(root, inOrder); // Size of inorder traversal storage vector int n = inOrder.Count; int l = 0, r = n - 1; // Traverse the array inorder using two pointers l // and r while (l < r) { int prod = inOrder[l] * inOrder[r]; // If product of elements at the two pointers is // k, return this as res if (prod == k) { res.Add(inOrder[l]); res.Add(inOrder[r]); break ; } // If prod is less than k, increase l as we have // to increase element value else if (prod < k) l++; // If prod is greater than k, decrease r as we // have to decrease element value else r--; } return res; } } public class GFG { // Driver code public static void Main( string [] args) { // Create the BST from Example 1 TreeNode root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right.left = new TreeNode(6); root.right.right = new TreeNode(10); int target = 24; Solution s = new Solution(); // Function call List< int > res = s.FindTarget(root, target); // Print the result if (res.Count == 2) Console.WriteLine(res[0] + " " + res[1]); else Console.WriteLine( "No such pair exists in the BST." ); } } // This code is contributed by Susobhan Akhuli |
Javascript
// Javascript program for the above approach // Definnition for a binnary tree node. class TreeNode { constructor(val) { this .val = val; this .left = this .right = null ; } } class Solution { // innorder traversal innorder(root, inn) { if (root === null ) return ; this .innorder(root.left, inn); inn.push(root.val); this .innorder(root.right, inn); } // Function to finnd two nodes inn the BST whose product equals to the target value finndTarget(root, k) { // To store the innorder traversal and result const inn = []; const res = []; this .innorder(root, inn); // Size of innorder traversal storage vector const n = inn.length; let l = 0, r = n - 1; // Traverse the array innorder usinng two poinnters l and r while (l < r) { const prod = inn[l] * inn[r]; // If product of element at the two poinnters is k, return this as res if (prod === k) { res.push(inn[l]); res.push(inn[r]); break ; } // If prod is less than inncrease l as we have to inncrease element value else if (prod < k) l++; // If prod is greater than decrease r as we have to decrease element value else r--; } return res; } } // Driver code const root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right.left = new TreeNode(6); root.right.right = new TreeNode(10); const target = 24; const s = new Solution(); // Function call const res = s.finndTarget(root, target); // Prinnt the result if (res.length === 2) { console.log(res[0], res[1]); } else { console.log( "No such pair exists inn the BST." ); } // This code is contributed by Susobhan Akhuli |
3 8
Time Complexity: O(N) where N is number of nodes in the given BST. This is because we are traversing each node once.
Space Complexity: O(N) as we are creating array of size N where N is number of nodes in the given BST.
Approach: This can be solved with the following idea:
- Perform inorder traversal for the BST from left to right and store the nodes in a stack.
- Perform inorder traversal for the BST from right to left and store the nodes in a stack.
- While either stack is not empty, get the top nodes of the two stacks.
- If the product of the top nodes is equal to the target value, then return the pair.
- If the product of the top nodes is less than the target value, then pop the top node from the left stack and move to its right subtree.
- If the product of the top nodes is greater than the target value, then pop the top node from the right stack and move to its left subtree.
- If no pair is found, return an empty vector.
Steps for the above approach:
- Create two stacks s1 and s2 for inorder traversal of the BST from left to right and right to left, respectively.
- Initialize current nodes curr1 and curr2 for the two in-order traversals, starting from the root of the BST.
- Loop until either stack is empty or a pair is found :
- Traverse the left subtree of the first tree (BST) and push each node onto s1 until curr1 becomes NULL.
- Traverse the right subtree of the second tree (BST) and push each node onto s2 until curr2 becomes NULL.
- If either stack is empty, break out of the loop.
- Get the top nodes of s1 and s2.
- If the product of the top nodes is equal to the target value, return the pair.
- If the product of the top nodes is less than the target value, pop the top node from s1 and move to its right subtree by setting curr1 = top1->right.
- If the product of the top nodes is greater than the target value, pop the top node from s2 and move to its left subtree by setting curr2 = top2->left.
- If no pair is found, return an empty vector.
Below is the code for the above approach :
C++
// C++ Implementation #include <iostream> #include <stack> #include <vector> using namespace std; // Definition for a binary tree node. struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode( int x) : val(x) , left(NULL) , right(NULL) { } }; class Solution { public : vector< int > findTarget(TreeNode* root, int k) { // To store the result vector< int > res; // Two stacks for inorder // traversal stack<TreeNode*> s1, s2; // Initialize current nodes // for inorder traversal TreeNode* curr1 = root; TreeNode* curr2 = root; // Loop until traversal // is complete while (curr1 != NULL || !s1.empty() || curr2 != NULL || !s2.empty()) { // Perform inorder traversal // for first tree (left to // right) while (curr1 != NULL) { s1.push(curr1); curr1 = curr1->left; } // Perform inorder traversal // for second tree (right // to left) while (curr2 != NULL) { s2.push(curr2); curr2 = curr2->right; } // If either stack is empty, // then traversal is complete if (s1.empty() || s2.empty()) break ; // Get the top nodes of // the two stacks TreeNode* top1 = s1.top(); TreeNode* top2 = s2.top(); // If the sum of the top nodes // is equal to k, then we // have found the required pair if (top1->val * top2->val == k) { res.push_back(top1->val); res.push_back(top2->val); break ; } // If the sum of the top // nodes is less than k, then // we need to move to the next // node in the first tree (curr1) else if (top1->val * top2->val < k) { s1.pop(); curr1 = top1->right; } // If the sum of the top nodes // is greater than k, then // we need to move to the next // node in the second tree (curr2) else { s2.pop(); curr2 = top2->left; } } return res; } }; // Driver code int main() { // Create the BST from Example 1 TreeNode* root = new TreeNode(5); root->left = new TreeNode(3); root->right = new TreeNode(8); root->left->left = new TreeNode(2); root->left->right = new TreeNode(4); root->right->left = new TreeNode(6); root->right->right = new TreeNode(10); int target = 24; Solution s; // Function call vector< int > res = s.findTarget(root, target); // Print the result if (res.size() == 2) cout << res[0] << " " << res[1] << endl; else cout << "No such pair exists in the BST." << endl; return 0; } |
Java
// Java Implementation import java.util.*; // Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right; TreeNode( int x) { val = x; left = null ; right = null ; } } class Solution { public List<Integer> findTarget(TreeNode root, int k) { // To store the result List<Integer> res = new ArrayList<>(); // Two stacks for inorder // traversal Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); // Initialize current nodes // for inorder traversal TreeNode curr1 = root; TreeNode curr2 = root; // Loop until traversal // is complete while (curr1 != null || !s1.empty() || curr2 != null || !s2.empty()) { // Perform inorder traversal // for first tree (left to // right) while (curr1 != null ) { s1.push(curr1); curr1 = curr1.left; } // Perform inorder traversal // for second tree (right to // left) while (curr2 != null ) { s2.push(curr2); curr2 = curr2.right; } // If either stack is empty, // then traversal is complete if (s1.empty() || s2.empty()) break ; // Get the top nodes of the two stacks TreeNode top1 = s1.peek(); TreeNode top2 = s2.peek(); // If the sum of the top nodes // is equal to k, then we have // found the required pair if (top1.val * top2.val == k) { res.add(top1.val); res.add(top2.val); break ; } // If the sum of the top // nodes is less than k, then // we need to move to the next // node in the first tree (curr1) else if (top1.val * top2.val < k) { s1.pop(); curr1 = top1.right; } // If the sum of the top nodes // is greater than k, then // we need to move to the next // node in the second tree (curr2) else { s2.pop(); curr2 = top2.left; } } return res; } } // Driver code class GFG { public static void main(String[] args) { // Create the BST from Example 1 TreeNode root = new TreeNode( 5 ); root.left = new TreeNode( 3 ); root.right = new TreeNode( 8 ); root.left.left = new TreeNode( 2 ); root.left.right = new TreeNode( 4 ); root.right.left = new TreeNode( 6 ); root.right.right = new TreeNode( 10 ); int target = 24 ; Solution s = new Solution(); // Function call List<Integer> res = s.findTarget(root, target); // Print the result if (res.size() == 2 ) System.out.println(res.get( 0 ) + " " + res.get( 1 )); else System.out.println( "No such pair exists in the BST." ); } } |
Python3
# Python Implementation # Definition for a binary tree node class TreeNode: def __init__( self , val = 0 , left = None , right = None ): self .val = val self .left = left self .right = right class Solution: def findTarget( self , root, k): # To store the result res = [] # Two stacks for inorder traversal s1, s2 = [], [] # Initialize current nodes for inorder traversal curr1, curr2 = root, root # Loop until traversal is complete while curr1 or s1 or curr2 or s2: # Perform inorder traversal for the first tree (left to right) while curr1: s1.append(curr1) curr1 = curr1.left # Perform inorder traversal for the second tree (right to left) while curr2: s2.append(curr2) curr2 = curr2.right # If either stack is empty, then traversal is complete if not s1 or not s2: break # Get the top nodes of the two stacks top1, top2 = s1[ - 1 ], s2[ - 1 ] # If the sum of the top nodes is equal to k, then we have found the required pair if top1.val * top2.val = = k: res.extend([top1.val, top2.val]) break # If the sum of the top nodes is less than k, then we need to move to the next node in the first tree (curr1) elif top1.val * top2.val < k: s1.pop() curr1 = top1.right # If the sum of the top nodes is greater than k, then we need to move to the next node in the second tree (curr2) else : s2.pop() curr2 = top2.left return res # Create the BST from Example 1 root = TreeNode( 5 ) root.left = TreeNode( 3 ) root.right = TreeNode( 8 ) root.left.left = TreeNode( 2 ) root.left.right = TreeNode( 4 ) root.right.left = TreeNode( 6 ) root.right.right = TreeNode( 10 ) target = 24 s = Solution() # Function call res = s.findTarget(root, target) # Print the result if len (res) = = 2 : print (res[ 0 ], res[ 1 ]) else : print ( "No such pair exists in the BST." ) # This code is contributed by Susobhan Akhuli |
C#
// C# code implementation: using System; using System.Collections.Generic; // Definition for a binary tree node. public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode( int x) { val = x; left = null ; right = null ; } } public class Solution { public List< int > FindTarget(TreeNode root, int k) { // To store the result List< int > res = new List< int >(); // Two stacks for inorder traversal Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); // Initialize current nodes for inorder traversal TreeNode curr1 = root; TreeNode curr2 = root; // Loop until traversal is complete while (curr1 != null || s1.Count > 0 || curr2 != null || s2.Count > 0) { // Perform inorder traversal for first tree // (left to right) while (curr1 != null ) { s1.Push(curr1); curr1 = curr1.left; } // Perform inorder traversal for second tree // (right to left) while (curr2 != null ) { s2.Push(curr2); curr2 = curr2.right; } // If either stack is empty, then traversal is // complete if (s1.Count == 0 || s2.Count == 0) break ; // Get the top nodes of the two stacks TreeNode top1 = s1.Peek(); TreeNode top2 = s2.Peek(); // If the sum of the top nodes is equal to k, // then we have found the required pair if (top1.val * top2.val == k) { res.Add(top1.val); res.Add(top2.val); break ; } // If the sum of the top nodes is less than k, // then we need to move to the next node in the // first tree (curr1) else if (top1.val * top2.val < k) { s1.Pop(); curr1 = top1.right; } // If the sum of the top nodes is greater than // k, then we need to move to the next node in // the second tree (curr2) else { s2.Pop(); curr2 = top2.left; } } return res; } } public class GFG { static public void Main() { // Code // Create the BST from Example 1 TreeNode root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right.left = new TreeNode(6); root.right.right = new TreeNode(10); int target = 24; Solution s = new Solution(); // Function call List< int > res = s.FindTarget(root, target); // Print the result if (res.Count == 2) Console.WriteLine(res[0] + " " + res[1]); else Console.WriteLine( "No such pair exists in the BST." ); } } // This code is contributed by karthik |
Javascript
<script> // JavaScript Implementation // Definition for a binary tree node. class TreeNode { constructor(val) { this .val = val; this .left = null ; this .right = null ; } } class Solution { findTarget(root, k) { // To store the result const res = []; // Two stacks for inorder traversal const s1 = []; const s2 = []; // Initialize current nodes for inorder traversal let curr1 = root; let curr2 = root; // Loop until traversal is complete while (curr1 !== null || s1.length !== 0 || curr2 !== null || s2.length !== 0) { // Perform inorder traversal for the first tree (left to right) while (curr1 !== null ) { s1.push(curr1); curr1 = curr1.left; } // Perform inorder traversal for the second tree (right to left) while (curr2 !== null ) { s2.push(curr2); curr2 = curr2.right; } // If either stack is empty, then traversal is complete if (s1.length === 0 || s2.length === 0) break ; // Get the top nodes of the two stacks const top1 = s1[s1.length - 1]; const top2 = s2[s2.length - 1]; // If the product of the top nodes is equal to k, then we have found the required pair if (top1.val * top2.val === k) { res.push(top1.val); res.push(top2.val); break ; } // If the product of the top nodes is less than k, move to the next node in the first tree (curr1) else if (top1.val * top2.val < k) { s1.pop(); curr1 = top1.right; } // If the product of the top nodes is greater than k, move to the next node in the second tree (curr2) else { s2.pop(); curr2 = top2.left; } } return res; } } // Driver code // Create the BST from Example 1 const root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right.left = new TreeNode(6); root.right.right = new TreeNode(10); const target = 24; const solution = new Solution(); // Function call const result = solution.findTarget(root, target); // Print the result if (result.length === 2) document.write(result[0] + " " + result[1]); else document.write( "No such pair exists in the BST." ); // This code is contributed by Susobhan Akhuli </script> |
3 8
Time Complexity: O(n), where n is the total number of nodes in the BST.
Auxiliary Space: O(h), where h is the height of the BST