{"id":"b3400213-0aa4-42d3-8fbd-c591243999ea","name":"Distance Between Two Nodes In A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of distanceBetweenNodes function. The function is expected to return the distance (in terms of number of edges) between two nodes in a generic tree.\r\nPlease watch the question video to understand what lca is.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n#include<climits>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data = 0;\n vector<Node *> children;\n\n Node(int data)\n {\n this->data = data;\n }\n};\n\n\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" Child: \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\n }\n}\n\nNode *constructor01(vector<int>arr)\n{\n if (arr.size() == 0)\n return NULL;\n\n vector<Node *> stack;\n stack.push_back(new Node(arr[0]));\n\n Node *root = stack[0];\n\n for (int i = 1; i < arr.size(); i++)\n {\n if (arr[i] != -1)\n {\n Node *node = stack.back();\n Node *nnode = new Node(arr[i]);\n\n node->children.push_back(nnode);\n stack.push_back(nnode);\n }\n else\n stack.pop_back();\n }\n return root;\n}\n\n\nvector<int> *rootNodeToPath(Node *node, int data)\n{\n\n if (node->data == data)\n {\n vector<int> *base = new vector<int>();\n base->push_back(data);\n return base;\n }\n\n vector<int> *ans = new vector<int>();\n for (Node *child : node->children)\n {\n vector<int> *recAns = rootNodeToPath(child, data);\n if (recAns->size() > 0)\n {\n recAns->push_back(node->data);\n return recAns;\n }\n }\n return ans;\n}\n\n\nint lca(Node *node, int data1, int data2)\n{\n vector<int> onePath = *rootNodeToPath(node, data1);\n vector<int> twoPath = *rootNodeToPath(node, data2);\n\n int i = onePath.size() - 1;\n int j = twoPath.size() - 1;\n bool flag = false;\n while (i >= 0 && j >= 0 && onePath[i] == twoPath[j])\n {\n flag = true;\n i--;\n j--;\n }\n\n int ans = 0;\n if (flag)\n {\n ans = onePath[i++];\n }\n return ans;\n}\n\n\nint distance(Node *node, int data1, int data2)\n{\n // Write your code here\n}\n\nvoid solve()\n{\n int n;\n cin>>n;\n vector<int>arr(n,0);\n for(int i = 0; i < n; i++)\n {\n cin>>arr[i];\n }\n \n int data1;\n cin>>data1;\n int data2;\n cin>>data2;\n \n Node *root = constructor01(arr);\n int dist = distance(root,data1,data2);\n cout<<dist<<endl;\n \n}\n\nint main()\n{\n solve();\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static ArrayList<Integer> nodeToRootPath(Node node, int data) {\r\n if (node.data == data) {\r\n ArrayList<Integer> path = new ArrayList<>();\r\n path.add(node.data);\r\n return path;\r\n }\r\n\r\n for (Node child : node.children) {\r\n ArrayList<Integer> ptc = nodeToRootPath(child, data);\r\n if (ptc.size() > 0) {\r\n ptc.add(node.data);\r\n return ptc;\r\n }\r\n }\r\n\r\n return new ArrayList<>();\r\n }\r\n\r\n public static int lca(Node node, int d1, int d2) {\r\n ArrayList<Integer> p1 = nodeToRootPath(node, d1);\r\n ArrayList<Integer> p2 = nodeToRootPath(node, d2);\r\n\r\n int i = p1.size() - 1;\r\n int j = p2.size() - 1;\r\n\r\n while(i >= 0 && j >= 0 && p1.get(i) == p2.get(j)){\r\n i--;\r\n j--;\r\n }\r\n\r\n return p1.get(i + 1);\r\n }\r\n\r\n public static int distanceBetweenNodes(Node node, int d1, int d2){\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 int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n int d1 = Integer.parseInt(br.readLine());\r\n int d2 = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n int dist = distanceBetweenNodes(root, d1, d2);\r\n System.out.println(dist);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self, data):\n self.data = data\n self.children = []\n\n# create a new tree node\n\ndef newNode(data):\n temp = Node(data)\n return temp \n\n\n# n-ary tree level wise\n\ndef constructor(lst, n):\n root = None\n stack = []\n for i in range(0, n) :\n if lst[i] == -1:\n stack.pop()\n else:\n t = Node(lst[i])\n if len(stack) > 0:\n stack[-1].children.append(t)\n\n else:\n root = t\n\n stack.append(t)\n\n return root\n\n\ndef nodeToRootPath(root,val):\n \n if root.data == val:\n \n base_ans = []\n base_ans.append(root.data)\n return base_ans\n\n \n for child in root.children:\n pt = nodeToRootPath(child,val)\n \n if len(pt) > 0:\n pt.append(root.data)\n return pt\n \n way = []\n return way\n\ndef lca(root, data1, data2):\n \n path1 = nodeToRootPath(root, data1)\n path2 = nodeToRootPath(root, data2)\n \n \n i = len(path1)-1\n j = len(path2)-1\n \n while i >= 0 and j >= 0 and path1[i] == path2[j]:\n i -= 1\n j -= 1\n \n return path1[i+1]\n \n \ndef distanceBetweenNodes(root, data1, data2):\n \n # Write your code here\n \n \n \n\n# main function\n\nif __name__ == \"__main__\":\n lst = [] \n n = int(input())\n lst = list(map(int, input().split(\" \")))\n \n data1 = int(input())\n data2 = int(input())\n \n root = constructor(lst, n)\n dist = distanceBetweenNodes(root, data1, data2)\n print(dist)"}},"points":10,"difficulty":"easy","sampleInput":"24\r\n10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1\r\n100\r\n110","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/1raYelrrhFM","hints":[],"associated":[{"id":"0a3698e6-d658-4b1e-ae23-e5241705bec2","name":"This question is based on which mentioned below concepts?","slug":"this-question-is-based-on-which-mentioned-below-concepts","type":4},{"id":"53e23b71-72c7-4a38-8b74-53f521a28e8e","name":"What will be the space complexity for \"Distance between 2 nodes of Generic tree\"?","slug":"what-will-be-the-space-complexity-for-distance-between-2-nodes-of-generic-tree","type":4},{"id":"712f644b-73f5-4bf0-8bf5-72d1aefb8448","name":"10 20 50 -1 60 -1 -1 30 70 -1 80 150 -1 120 -1 -1 90 -1 -1 40 109 -1 -1 -1 109 150 What will be the distance between 109 and 150?","slug":"10-20-50-1-60-1-1-30-70-1-80-150-1-120-1-1-90-1-1-40-109-1-1-1-109-150-what-will-be-the-distance-between-109-and-150","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":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"76e9de27-d5dd-42b6-b71c-d3263f467439","name":"Distance Between Two Nodes In A Generic Tree","slug":"distance-between-two-nodes-in-a-generic-tree","type":1}],"next":{"id":"50c4f981-2356-446d-af31-99af683b1d42","name":"Distance Between Two Nodes In A Generic Tree","type":3,"slug":"distance-between-two-nodes-in-a-generic-tree"},"prev":{"id":"e54f1209-5cb9-47aa-9892-9f9161819a8e","name":"Lowest Common Ancestor - Generic Tree","type":3,"slug":"lowest-common-ancestor-generic-tree"}}}

Distance Between Two Nodes In A Generic Tree

1. You are given a partially written GenericTree class. 2. You are required to complete the body of distanceBetweenNodes function. The function is expected to return the distance (in terms of number of edges) between two nodes in a generic tree. Please watch the question video to understand what lca is. 3. Input and Output is managed for you.

{"id":"b3400213-0aa4-42d3-8fbd-c591243999ea","name":"Distance Between Two Nodes In A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of distanceBetweenNodes function. The function is expected to return the distance (in terms of number of edges) between two nodes in a generic tree.\r\nPlease watch the question video to understand what lca is.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n#include<climits>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data = 0;\n vector<Node *> children;\n\n Node(int data)\n {\n this->data = data;\n }\n};\n\n\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" Child: \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\n }\n}\n\nNode *constructor01(vector<int>arr)\n{\n if (arr.size() == 0)\n return NULL;\n\n vector<Node *> stack;\n stack.push_back(new Node(arr[0]));\n\n Node *root = stack[0];\n\n for (int i = 1; i < arr.size(); i++)\n {\n if (arr[i] != -1)\n {\n Node *node = stack.back();\n Node *nnode = new Node(arr[i]);\n\n node->children.push_back(nnode);\n stack.push_back(nnode);\n }\n else\n stack.pop_back();\n }\n return root;\n}\n\n\nvector<int> *rootNodeToPath(Node *node, int data)\n{\n\n if (node->data == data)\n {\n vector<int> *base = new vector<int>();\n base->push_back(data);\n return base;\n }\n\n vector<int> *ans = new vector<int>();\n for (Node *child : node->children)\n {\n vector<int> *recAns = rootNodeToPath(child, data);\n if (recAns->size() > 0)\n {\n recAns->push_back(node->data);\n return recAns;\n }\n }\n return ans;\n}\n\n\nint lca(Node *node, int data1, int data2)\n{\n vector<int> onePath = *rootNodeToPath(node, data1);\n vector<int> twoPath = *rootNodeToPath(node, data2);\n\n int i = onePath.size() - 1;\n int j = twoPath.size() - 1;\n bool flag = false;\n while (i >= 0 && j >= 0 && onePath[i] == twoPath[j])\n {\n flag = true;\n i--;\n j--;\n }\n\n int ans = 0;\n if (flag)\n {\n ans = onePath[i++];\n }\n return ans;\n}\n\n\nint distance(Node *node, int data1, int data2)\n{\n // Write your code here\n}\n\nvoid solve()\n{\n int n;\n cin>>n;\n vector<int>arr(n,0);\n for(int i = 0; i < n; i++)\n {\n cin>>arr[i];\n }\n \n int data1;\n cin>>data1;\n int data2;\n cin>>data2;\n \n Node *root = constructor01(arr);\n int dist = distance(root,data1,data2);\n cout<<dist<<endl;\n \n}\n\nint main()\n{\n solve();\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static ArrayList<Integer> nodeToRootPath(Node node, int data) {\r\n if (node.data == data) {\r\n ArrayList<Integer> path = new ArrayList<>();\r\n path.add(node.data);\r\n return path;\r\n }\r\n\r\n for (Node child : node.children) {\r\n ArrayList<Integer> ptc = nodeToRootPath(child, data);\r\n if (ptc.size() > 0) {\r\n ptc.add(node.data);\r\n return ptc;\r\n }\r\n }\r\n\r\n return new ArrayList<>();\r\n }\r\n\r\n public static int lca(Node node, int d1, int d2) {\r\n ArrayList<Integer> p1 = nodeToRootPath(node, d1);\r\n ArrayList<Integer> p2 = nodeToRootPath(node, d2);\r\n\r\n int i = p1.size() - 1;\r\n int j = p2.size() - 1;\r\n\r\n while(i >= 0 && j >= 0 && p1.get(i) == p2.get(j)){\r\n i--;\r\n j--;\r\n }\r\n\r\n return p1.get(i + 1);\r\n }\r\n\r\n public static int distanceBetweenNodes(Node node, int d1, int d2){\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 int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n int d1 = Integer.parseInt(br.readLine());\r\n int d2 = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n int dist = distanceBetweenNodes(root, d1, d2);\r\n System.out.println(dist);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self, data):\n self.data = data\n self.children = []\n\n# create a new tree node\n\ndef newNode(data):\n temp = Node(data)\n return temp \n\n\n# n-ary tree level wise\n\ndef constructor(lst, n):\n root = None\n stack = []\n for i in range(0, n) :\n if lst[i] == -1:\n stack.pop()\n else:\n t = Node(lst[i])\n if len(stack) > 0:\n stack[-1].children.append(t)\n\n else:\n root = t\n\n stack.append(t)\n\n return root\n\n\ndef nodeToRootPath(root,val):\n \n if root.data == val:\n \n base_ans = []\n base_ans.append(root.data)\n return base_ans\n\n \n for child in root.children:\n pt = nodeToRootPath(child,val)\n \n if len(pt) > 0:\n pt.append(root.data)\n return pt\n \n way = []\n return way\n\ndef lca(root, data1, data2):\n \n path1 = nodeToRootPath(root, data1)\n path2 = nodeToRootPath(root, data2)\n \n \n i = len(path1)-1\n j = len(path2)-1\n \n while i >= 0 and j >= 0 and path1[i] == path2[j]:\n i -= 1\n j -= 1\n \n return path1[i+1]\n \n \ndef distanceBetweenNodes(root, data1, data2):\n \n # Write your code here\n \n \n \n\n# main function\n\nif __name__ == \"__main__\":\n lst = [] \n n = int(input())\n lst = list(map(int, input().split(\" \")))\n \n data1 = int(input())\n data2 = int(input())\n \n root = constructor(lst, n)\n dist = distanceBetweenNodes(root, data1, data2)\n print(dist)"}},"points":10,"difficulty":"easy","sampleInput":"24\r\n10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1\r\n100\r\n110","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/1raYelrrhFM","hints":[],"associated":[{"id":"0a3698e6-d658-4b1e-ae23-e5241705bec2","name":"This question is based on which mentioned below concepts?","slug":"this-question-is-based-on-which-mentioned-below-concepts","type":4},{"id":"53e23b71-72c7-4a38-8b74-53f521a28e8e","name":"What will be the space complexity for \"Distance between 2 nodes of Generic tree\"?","slug":"what-will-be-the-space-complexity-for-distance-between-2-nodes-of-generic-tree","type":4},{"id":"712f644b-73f5-4bf0-8bf5-72d1aefb8448","name":"10 20 50 -1 60 -1 -1 30 70 -1 80 150 -1 120 -1 -1 90 -1 -1 40 109 -1 -1 -1 109 150 What will be the distance between 109 and 150?","slug":"10-20-50-1-60-1-1-30-70-1-80-150-1-120-1-1-90-1-1-40-109-1-1-1-109-150-what-will-be-the-distance-between-109-and-150","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":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"76e9de27-d5dd-42b6-b71c-d3263f467439","name":"Distance Between Two Nodes In A Generic Tree","slug":"distance-between-two-nodes-in-a-generic-tree","type":1}],"next":{"id":"50c4f981-2356-446d-af31-99af683b1d42","name":"Distance Between Two Nodes In A Generic Tree","type":3,"slug":"distance-between-two-nodes-in-a-generic-tree"},"prev":{"id":"e54f1209-5cb9-47aa-9892-9f9161819a8e","name":"Lowest Common Ancestor - Generic Tree","type":3,"slug":"lowest-common-ancestor-generic-tree"}}}
plane

Editor

Loading...

Distance Between Two Nodes In A Generic Tree

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of distanceBetweenNodes function. The function is expected to return the distance (in terms of number of edges) between two nodes in a generic tree. Please watch the question video to understand what lca is. 3. Input and Output is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1 100 110

Sample Output

5

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode