`{"id":"4f805266-e3fe-4e71-8a7f-440741160247","name":"Target Sum Pair In Bst","description":"<p>1. You are given a partially written BST class. 2. You are given a value. You are required to print all pair of nodes which add up to the given value. Make sure all pairs print the smaller value first and avoid duplicacies. Make sure to print the pairs in increasing order. Use the question video to gain clarity. 3. Input and Output is managed for you.</p>","inputFormat":"Input is managed for you","outputFormat":"\"smaller node\" \"larger node\"\r\n.. all pairs that add to target on separate lines","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <stack>\n#include <string>\n\nusing namespace std;\n\nclass Node{\npublic:\n int data;\n Node * left = nullptr; \n Node * right = nullptr;\n Node (int data)\n {\n this->data=data;\n }\n};\n\nclass Pair{\n Node *node = nullptr;\n int state=0;\n\n Pair(Node *node, int state) {\n this->node = node;\n this->state = state;\n }\n};\n\nNode* construct(vector<int> & arr) {\n Node* root = new Node(arr);\n pair<Node*, int> p = {root, 1};\n\n stack<pair<Node*, int>> st;\n st.push(p);\n\n int idx = 1;\n while (!st.empty()) {\n if (st.top().second == 1) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->left = new Node(arr[idx]);\n pair<Node*, int> lp = {st.top().first->left, 1};\n st.push(lp);\n }\n else {\n st.top().first->left = nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*, int> rp = {st.top().first->right, 1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\n\n void travelAndPrint(Node * root , Node * node , int tar){\n \n //write your code here\n \n }\n\n int main() {\n int n;\n cin>>n;\n vector<int> arr(n,0);\n \n for(int i = 0; i < n; i++) {\n string tmp;\n cin>>tmp;\n if (tmp==\"n\") {\n arr[i] = -1;\n } else {\n arr[i] = stoi(tmp);\n }\n }\n\n int k1;\n cin>>k1;\n\n Node* root = construct(arr);\n travelAndPrint(root,root,k1);\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr, null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n int data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self, data,left,right):\n self.data = data\n self.left = left\n self.right = right\n \nclass Pair:\n def __init__(self,node,st):\n self.node=node;\n self.state=st;\n \n\ndef construct(arr):\n root=Node(arr,None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n top.state+=1\n else:\n st.pop();\n return root;\n \n\ndef travelAndPrint(node ,tar):\n #write your code here\n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nd1=int(input())\nroot=construct(arr)\ntravelAndPrint(root,d1)"}},"points":10,"difficulty":"easy","sampleInput":"21\r\n50 25 12 n n 37 30 n n n 75 62 60 n n 70 n n 87 n n\r\n100","sampleOutput":"25 75\r\n30 70","questionVideo":"https://www.youtube.com/embed/FH7gpdOgc88","hints":[],"associated":[{"id":"6c3bc0f8-56f0-4e32-b975-3a922f66ef5c","name":"Calling the right subtree first in the inorder traversal would sort the result in descending order, as well as sort the pairs in descending order.","slug":"calling-the-right-subtree-first-in-the-inorder-traversal-would-sort-the-result-in-descending-order-as-well-as-sort-the-pairs-in-descending-order","type":4},{"id":"78cd9e5c-f590-45ee-89cb-8d887e6740b3","name":"Changing the signs in the condition","slug":"changing-the-signs-in-the-condition","type":4},{"id":"c24598e8-aa7d-4e9d-b4c8-f62374b7d766","name":"Which traversal is implemented in the \"Find complement\" solution?","slug":"which-traversal-is-implemented-in-the-find-complement-solution","type":4},{"id":"cf906c64-49cf-400b-a055-29c20585154f","name":"Out of all 3 approaches, what is the best worst-case time complexity?","slug":"out-of-all-3-approaches-what-is-the-best-worst-case-time-complexity","type":4},{"id":"e86efd90-542a-49bd-a76f-b38321225fa1","name":"How is the complement of the number calculated in the \"Find complement\" approach?","slug":"how-is-the-complement-of-the-number-calculated-in-the-find-complement-approach","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"d27c8e3e-b9d7-4eec-9b68-798d9f9f93ce","name":"Target Sum Pair In Bst","slug":"target-sum-pair-in-bst","type":1}],"next":{"id":"0214bfea-3466-4773-8fa9-70918d94ee90","name":"Target Sum Pair In Bst","type":3,"slug":"target-sum-pair-in-bst"},"prev":{"id":"2d1ee10a-b7bb-4748-8594-4eeb5d456332","name":"Print In Range","type":3,"slug":"print-in-range"}}}`

# Target Sum Pair In Bst

<p>1. You are given a partially written BST class. 2. You are given a value. You are required to print all pair of nodes which add up to the given value. Make sure all pairs print the smaller value first and avoid duplicacies. Make sure to print the pairs in increasing order. Use the question video to gain clarity. 3. Input and Output is managed for you.</p>

`{"id":"4f805266-e3fe-4e71-8a7f-440741160247","name":"Target Sum Pair In Bst","description":"<p>1. You are given a partially written BST class. 2. You are given a value. You are required to print all pair of nodes which add up to the given value. Make sure all pairs print the smaller value first and avoid duplicacies. Make sure to print the pairs in increasing order. Use the question video to gain clarity. 3. Input and Output is managed for you.</p>","inputFormat":"Input is managed for you","outputFormat":"\"smaller node\" \"larger node\"\r\n.. all pairs that add to target on separate lines","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <stack>\n#include <string>\n\nusing namespace std;\n\nclass Node{\npublic:\n int data;\n Node * left = nullptr; \n Node * right = nullptr;\n Node (int data)\n {\n this->data=data;\n }\n};\n\nclass Pair{\n Node *node = nullptr;\n int state=0;\n\n Pair(Node *node, int state) {\n this->node = node;\n this->state = state;\n }\n};\n\nNode* construct(vector<int> & arr) {\n Node* root = new Node(arr);\n pair<Node*, int> p = {root, 1};\n\n stack<pair<Node*, int>> st;\n st.push(p);\n\n int idx = 1;\n while (!st.empty()) {\n if (st.top().second == 1) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->left = new Node(arr[idx]);\n pair<Node*, int> lp = {st.top().first->left, 1};\n st.push(lp);\n }\n else {\n st.top().first->left = nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*, int> rp = {st.top().first->right, 1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\n\n void travelAndPrint(Node * root , Node * node , int tar){\n \n //write your code here\n \n }\n\n int main() {\n int n;\n cin>>n;\n vector<int> arr(n,0);\n \n for(int i = 0; i < n; i++) {\n string tmp;\n cin>>tmp;\n if (tmp==\"n\") {\n arr[i] = -1;\n } else {\n arr[i] = stoi(tmp);\n }\n }\n\n int k1;\n cin>>k1;\n\n Node* root = construct(arr);\n travelAndPrint(root,root,k1);\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr, null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n int data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self, data,left,right):\n self.data = data\n self.left = left\n self.right = right\n \nclass Pair:\n def __init__(self,node,st):\n self.node=node;\n self.state=st;\n \n\ndef construct(arr):\n root=Node(arr,None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n top.state+=1\n else:\n st.pop();\n return root;\n \n\ndef travelAndPrint(node ,tar):\n #write your code here\n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nd1=int(input())\nroot=construct(arr)\ntravelAndPrint(root,d1)"}},"points":10,"difficulty":"easy","sampleInput":"21\r\n50 25 12 n n 37 30 n n n 75 62 60 n n 70 n n 87 n n\r\n100","sampleOutput":"25 75\r\n30 70","questionVideo":"https://www.youtube.com/embed/FH7gpdOgc88","hints":[],"associated":[{"id":"6c3bc0f8-56f0-4e32-b975-3a922f66ef5c","name":"Calling the right subtree first in the inorder traversal would sort the result in descending order, as well as sort the pairs in descending order.","slug":"calling-the-right-subtree-first-in-the-inorder-traversal-would-sort-the-result-in-descending-order-as-well-as-sort-the-pairs-in-descending-order","type":4},{"id":"78cd9e5c-f590-45ee-89cb-8d887e6740b3","name":"Changing the signs in the condition","slug":"changing-the-signs-in-the-condition","type":4},{"id":"c24598e8-aa7d-4e9d-b4c8-f62374b7d766","name":"Which traversal is implemented in the \"Find complement\" solution?","slug":"which-traversal-is-implemented-in-the-find-complement-solution","type":4},{"id":"cf906c64-49cf-400b-a055-29c20585154f","name":"Out of all 3 approaches, what is the best worst-case time complexity?","slug":"out-of-all-3-approaches-what-is-the-best-worst-case-time-complexity","type":4},{"id":"e86efd90-542a-49bd-a76f-b38321225fa1","name":"How is the complement of the number calculated in the \"Find complement\" approach?","slug":"how-is-the-complement-of-the-number-calculated-in-the-find-complement-approach","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"d27c8e3e-b9d7-4eec-9b68-798d9f9f93ce","name":"Target Sum Pair In Bst","slug":"target-sum-pair-in-bst","type":1}],"next":{"id":"0214bfea-3466-4773-8fa9-70918d94ee90","name":"Target Sum Pair In Bst","type":3,"slug":"target-sum-pair-in-bst"},"prev":{"id":"2d1ee10a-b7bb-4748-8594-4eeb5d456332","name":"Print In Range","type":3,"slug":"print-in-range"}}}` Editor

# Target Sum Pair In Bst

easy

1. You are given a partially written BST class. 2. You are given a value. You are required to print all pair of nodes which add up to the given value. Make sure all pairs print the smaller value first and avoid duplicacies. Make sure to print the pairs in increasing order. Use the question video to gain clarity. 3. Input and Output is managed for you.

None

## Format

### Input

Input is managed for you

### Output

"smaller node" "larger node" .. all pairs that add to target on separate lines

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}21 50 25 12 n n 37 30 n n n 75 62 60 n n 70 n n 87 n n 100```

### Sample Output

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}25 75 30 70```

Question Video

Discussions

Show Discussion

Related Resources 