{"id":"819d1797-fb4b-41ba-8f5f-bcbb7d9d8658","name":"Print Nodes K Distance Away","description":"1. You are given a partially written BinaryTree class.\r\n2. You are given a value data and a value k.\r\n3. You are required to complete the body of printKNodesFar function. The function is expected to print all nodes which are k distance away in any direction from node with value equal to data.\r\n4. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"All nodes which are k distance away in any direction from node with value equal to data, each in a separate line","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <queue>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data,Node *left,Node *right)\n {\n this->data = data;\n this->left = left;\n this->right = right;\n }\n};\n\nint idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++],nullptr,nullptr);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvector<Node*> nodeToRootPath(Node *node, int data) {\n vector<Node*> temp;\n if (node == nullptr){\n return temp;\n }\n\n vector<Node*> ans;\n if(node->data == data) {\n ans.push_back(node);\n return ans;\n }\n vector<Node*> left = nodeToRootPath(node->left, data);\n if(left.size() > 0) {\n left.push_back(node);\n return left;\n }\n vector<Node*> right = nodeToRootPath(node->right, data);\n if(right.size() > 0) {\n right.push_back(node);\n return right;\n }\n return temp;\n }\n\n\nvoid printKLevelsDown(Node *node, int k, Node *block)\n{\n if (node == nullptr || node == block)\n return;\n\n if (k == 0)\n {\n cout << node->data <<endl;\n return;\n }\n\n printKLevelsDown(node->left, k - 1, block);\n printKLevelsDown(node->right, k - 1, block);\n}\n\nvoid printKNodesFar(Node *node, int data,int k)\n{\n // write your code here\n}\n\nint main()\n{\n vector<int> arr;\n int n;\n cin>>n;\n \n for(int i = 0; i<n; i++){\n string inp;\n cin>>inp;\n if(inp != \"n\"){\n arr.push_back(stoi(inp));\n }\n else{\n arr.push_back(-1);\n }\n }\n\n int data;\n cin>>data;\n int k;\n cin>>k;\n Node *root = constructTree(arr);\n printKNodesFar(root, data, k);\n \n return 0;\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[0], 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 printKNodesFar(Node node, int data, int k) {\r\n // write your code here\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 int k = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n printKNodesFar(root, data, k);\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\nidx = 0\n\ndef construct(arr):\n global idx\n if idx == len(arr) or arr[idx] == -1:\n idx = idx+1\n return None\n node = Node(arr[idx],None,None)\n idx = idx+1\n node.left = construct(arr)\n node.right = construct(arr)\n return node\n\ndef nodeToRootPath(node,data):\n if node == None:\n return []\n ans = []\n if(node.data == data):\n ans.append(node)\n return ans\n left = nodeToRootPath(node.left,data)\n if len(left) > 0:\n left.append(node)\n return left\n \n right = nodeToRootPath(node.right,data)\n if len(right) > 0:\n right.append(node)\n return right\n return []\n\ndef printKLevelDown(node,k,block):\n if node == None:\n return\n if node == block:\n return\n if k == 0:\n print(node.data)\n return\n printKLevelDown(node.left,k-1,block)\n printKLevelDown(node.right,k-1,block)\n\ndef printKNodesFar(node,data,k):\n # write your code here\n \n\ndef display(node):\n if node:\n s = \"\"\n s += \".\" if node.left == None else str(node.left.data)\n s += \" <- \" + str(node.data) + \" -> \"\n s += \".\" if node.right == None else str(node.right.data)\n print(s)\n display(node.left)\n display(node.right)\n\n\nif __name__ == '__main__':\n\n n = int(input())\n s = input()\n l = list(s.split(\" \"))\n arr = []\n for i in range(len(l)):\n if(l[i] == 'n'):\n arr.append(-1)\n \n elif(l[i] == 'n\\r'):\n arr.append(-1)\n \n else:\n arr.append(int(l[i]))\n \n data = int(input())\n k = int(input())\n\n\n root = construct(arr)\n #display(root)\n printKNodesFar(root,data,k)"}},"points":10,"difficulty":"easy","sampleInput":"19\r\n50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n\r\n37\r\n2","sampleOutput":"12\r\n50","questionVideo":"https://www.youtube.com/embed/cH8gtWOrTGY","hints":[],"associated":[{"id":"1807e799-aeb3-4f7b-aded-d7776622d9e2","name":"When you are passing to its subtree","slug":"when-you-are-passing-to-its-subtree","type":4},{"id":"787c39b9-8719-4913-b6db-b0f8431b3d2b","name":"If K distance == 0 at every node then","slug":"if-k-distance-0-at-every-node-then","type":4},{"id":"7b59c4d7-8a6f-4766-adb2-61d477789fcf","name":"What is the expected auxiliary space of solving print nodes k distance away?","slug":"what-is-the-expected-auxiliary-space-of-solving-print-nodes-k-distance-away","type":4},{"id":"f1f01022-0c0f-47f2-8285-ea6a8ce049a3","name":"What is the time complexity of solving print nodes k distance away?","slug":"what-is-the-time-complexity-of-solving-print-nodes-k-distance-away","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":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"8c279645-24b7-44d1-9982-98bebb21a033","name":"Print Nodes K Distance Away","slug":"print-nodes-k-distance-away","type":1}],"next":{"id":"cef67655-4d98-422d-a4e6-1c574a5685ec","name":"Print Nodes K Distance Away","type":3,"slug":"print-nodes-k-distance-away"},"prev":{"id":"2f7310d1-f4c2-4e9d-ba7f-51a597f189e2","name":"Print K Levels Down","type":3,"slug":"print-k-levels-down"}}}

Print Nodes K Distance Away

1. You are given a partially written BinaryTree class. 2. You are given a value data and a value k. 3. You are required to complete the body of printKNodesFar function. The function is expected to print all nodes which are k distance away in any direction from node with value equal to data. 4. Input is managed for you.

{"id":"819d1797-fb4b-41ba-8f5f-bcbb7d9d8658","name":"Print Nodes K Distance Away","description":"1. You are given a partially written BinaryTree class.\r\n2. You are given a value data and a value k.\r\n3. You are required to complete the body of printKNodesFar function. The function is expected to print all nodes which are k distance away in any direction from node with value equal to data.\r\n4. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"All nodes which are k distance away in any direction from node with value equal to data, each in a separate line","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <queue>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data,Node *left,Node *right)\n {\n this->data = data;\n this->left = left;\n this->right = right;\n }\n};\n\nint idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++],nullptr,nullptr);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvector<Node*> nodeToRootPath(Node *node, int data) {\n vector<Node*> temp;\n if (node == nullptr){\n return temp;\n }\n\n vector<Node*> ans;\n if(node->data == data) {\n ans.push_back(node);\n return ans;\n }\n vector<Node*> left = nodeToRootPath(node->left, data);\n if(left.size() > 0) {\n left.push_back(node);\n return left;\n }\n vector<Node*> right = nodeToRootPath(node->right, data);\n if(right.size() > 0) {\n right.push_back(node);\n return right;\n }\n return temp;\n }\n\n\nvoid printKLevelsDown(Node *node, int k, Node *block)\n{\n if (node == nullptr || node == block)\n return;\n\n if (k == 0)\n {\n cout << node->data <<endl;\n return;\n }\n\n printKLevelsDown(node->left, k - 1, block);\n printKLevelsDown(node->right, k - 1, block);\n}\n\nvoid printKNodesFar(Node *node, int data,int k)\n{\n // write your code here\n}\n\nint main()\n{\n vector<int> arr;\n int n;\n cin>>n;\n \n for(int i = 0; i<n; i++){\n string inp;\n cin>>inp;\n if(inp != \"n\"){\n arr.push_back(stoi(inp));\n }\n else{\n arr.push_back(-1);\n }\n }\n\n int data;\n cin>>data;\n int k;\n cin>>k;\n Node *root = constructTree(arr);\n printKNodesFar(root, data, k);\n \n return 0;\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[0], 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 printKNodesFar(Node node, int data, int k) {\r\n // write your code here\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 int k = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n printKNodesFar(root, data, k);\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\nidx = 0\n\ndef construct(arr):\n global idx\n if idx == len(arr) or arr[idx] == -1:\n idx = idx+1\n return None\n node = Node(arr[idx],None,None)\n idx = idx+1\n node.left = construct(arr)\n node.right = construct(arr)\n return node\n\ndef nodeToRootPath(node,data):\n if node == None:\n return []\n ans = []\n if(node.data == data):\n ans.append(node)\n return ans\n left = nodeToRootPath(node.left,data)\n if len(left) > 0:\n left.append(node)\n return left\n \n right = nodeToRootPath(node.right,data)\n if len(right) > 0:\n right.append(node)\n return right\n return []\n\ndef printKLevelDown(node,k,block):\n if node == None:\n return\n if node == block:\n return\n if k == 0:\n print(node.data)\n return\n printKLevelDown(node.left,k-1,block)\n printKLevelDown(node.right,k-1,block)\n\ndef printKNodesFar(node,data,k):\n # write your code here\n \n\ndef display(node):\n if node:\n s = \"\"\n s += \".\" if node.left == None else str(node.left.data)\n s += \" <- \" + str(node.data) + \" -> \"\n s += \".\" if node.right == None else str(node.right.data)\n print(s)\n display(node.left)\n display(node.right)\n\n\nif __name__ == '__main__':\n\n n = int(input())\n s = input()\n l = list(s.split(\" \"))\n arr = []\n for i in range(len(l)):\n if(l[i] == 'n'):\n arr.append(-1)\n \n elif(l[i] == 'n\\r'):\n arr.append(-1)\n \n else:\n arr.append(int(l[i]))\n \n data = int(input())\n k = int(input())\n\n\n root = construct(arr)\n #display(root)\n printKNodesFar(root,data,k)"}},"points":10,"difficulty":"easy","sampleInput":"19\r\n50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n\r\n37\r\n2","sampleOutput":"12\r\n50","questionVideo":"https://www.youtube.com/embed/cH8gtWOrTGY","hints":[],"associated":[{"id":"1807e799-aeb3-4f7b-aded-d7776622d9e2","name":"When you are passing to its subtree","slug":"when-you-are-passing-to-its-subtree","type":4},{"id":"787c39b9-8719-4913-b6db-b0f8431b3d2b","name":"If K distance == 0 at every node then","slug":"if-k-distance-0-at-every-node-then","type":4},{"id":"7b59c4d7-8a6f-4766-adb2-61d477789fcf","name":"What is the expected auxiliary space of solving print nodes k distance away?","slug":"what-is-the-expected-auxiliary-space-of-solving-print-nodes-k-distance-away","type":4},{"id":"f1f01022-0c0f-47f2-8285-ea6a8ce049a3","name":"What is the time complexity of solving print nodes k distance away?","slug":"what-is-the-time-complexity-of-solving-print-nodes-k-distance-away","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":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"8c279645-24b7-44d1-9982-98bebb21a033","name":"Print Nodes K Distance Away","slug":"print-nodes-k-distance-away","type":1}],"next":{"id":"cef67655-4d98-422d-a4e6-1c574a5685ec","name":"Print Nodes K Distance Away","type":3,"slug":"print-nodes-k-distance-away"},"prev":{"id":"2f7310d1-f4c2-4e9d-ba7f-51a597f189e2","name":"Print K Levels Down","type":3,"slug":"print-k-levels-down"}}}
plane

Editor

Loading...

Print Nodes K Distance Away

easy

1. You are given a partially written BinaryTree class. 2. You are given a value data and a value k. 3. You are required to complete the body of printKNodesFar function. The function is expected to print all nodes which are k distance away in any direction from node with value equal to data. 4. Input is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

All nodes which are k distance away in any direction from node with value equal to data, each in a separate line

Example

Sample Input

19 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n 37 2

Sample Output

12 50

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode