{"id":"2e4a16d2-8dc4-4c68-9925-1fb235cde8fb","name":"Transform To Left-cloned Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of createLeftCloneTree function. The function is expected to create a new node for every node equal in value to it and inserted between itself and it's left child. Check question video for clarity.\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 <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\n int 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\nvoid display(Node *node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \"\";\n str += node->left == nullptr ? \".\" : to_string(node->left->data) + \"\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right == nullptr ? \".\" : to_string(node->right->data) + \"\";\n cout<<str<<endl;\n\n display(node->left);\n display(node->right);\n}\n\n\n Node *createLeftCloneTree(Node *node){\n // write your code here\n\n }\n \n int 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 \n Node *root = constructTree(arr);\n root = createLeftCloneTree(root);\n display(root);\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 Node createLeftCloneTree(Node node){\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 Node root = construct(arr);\r\n root = createLeftCloneTree(root);\r\n display(root);\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\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\ndef createLeftCloneTree(node):\n # write your code here\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 root = construct(arr)\n root = createLeftCloneTree(root)\n display(root)"}},"points":10,"difficulty":"easy","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n","sampleOutput":"50 <- 50 -> 75\r\n25 <- 50 -> .\r\n25 <- 25 -> 37\r\n12 <- 25 -> .\r\n12 <- 12 -> .\r\n. <- 12 -> .\r\n37 <- 37 -> .\r\n. <- 37 -> .\r\n75 <- 75 -> 87\r\n62 <- 75 -> .\r\n62 <- 62 -> .\r\n. <- 62 -> .\r\n87 <- 87 -> .\r\n. <- 87 -> .","questionVideo":"https://www.youtube.com/embed/jEYKDu4iyik","hints":[],"associated":[{"id":"34e1c812-3c3e-48c8-816d-467f7acd5cb9","name":"How mayny traversal orders are their in Binary Tree?","slug":"how-mayny-traversal-orders-are-their-in-binary-tree","type":4},{"id":"89830c2e-4697-4767-8d21-0a0e3a75128d","name":"Do binary tree have more then 2 children?","slug":"do-binary-tree-have-more-then-2-children","type":4},{"id":"e8acb453-daf6-49ad-a338-5990c57200cf","name":"In which order will the work go on?","slug":"in-which-order-will-the-work-go-on","type":4},{"id":"e9173585-f91c-42c7-9dde-edee0ed70f79","name":"What will be the base case here?","slug":"what-will-be-the-base-case-here","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":"04cc08c6-5137-43c2-8300-13379999c3c5","name":"Transform To Left-cloned Tree","slug":"transform-to-left-cloned-tree","type":1}],"next":{"id":"1a1cea30-6e50-4619-b1f4-631cfd5763ec","name":"Transform to Left Cloned Tree","type":3,"slug":"transform-to-left-cloned-tree"},"prev":{"id":"31a390f5-774e-4837-8e2d-c5ac99d34fd5","name":"Path to Leaf From Root in Range","type":3,"slug":"path-to-leaf-from-root-in-range"}}}

Transform To Left-cloned Tree

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of createLeftCloneTree function. The function is expected to create a new node for every node equal in value to it and inserted between itself and it's left child. Check question video for clarity. 3. Input and Output is managed for you.

{"id":"2e4a16d2-8dc4-4c68-9925-1fb235cde8fb","name":"Transform To Left-cloned Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of createLeftCloneTree function. The function is expected to create a new node for every node equal in value to it and inserted between itself and it's left child. Check question video for clarity.\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 <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\n int 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\nvoid display(Node *node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \"\";\n str += node->left == nullptr ? \".\" : to_string(node->left->data) + \"\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right == nullptr ? \".\" : to_string(node->right->data) + \"\";\n cout<<str<<endl;\n\n display(node->left);\n display(node->right);\n}\n\n\n Node *createLeftCloneTree(Node *node){\n // write your code here\n\n }\n \n int 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 \n Node *root = constructTree(arr);\n root = createLeftCloneTree(root);\n display(root);\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 Node createLeftCloneTree(Node node){\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 Node root = construct(arr);\r\n root = createLeftCloneTree(root);\r\n display(root);\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\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\ndef createLeftCloneTree(node):\n # write your code here\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 root = construct(arr)\n root = createLeftCloneTree(root)\n display(root)"}},"points":10,"difficulty":"easy","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n","sampleOutput":"50 <- 50 -> 75\r\n25 <- 50 -> .\r\n25 <- 25 -> 37\r\n12 <- 25 -> .\r\n12 <- 12 -> .\r\n. <- 12 -> .\r\n37 <- 37 -> .\r\n. <- 37 -> .\r\n75 <- 75 -> 87\r\n62 <- 75 -> .\r\n62 <- 62 -> .\r\n. <- 62 -> .\r\n87 <- 87 -> .\r\n. <- 87 -> .","questionVideo":"https://www.youtube.com/embed/jEYKDu4iyik","hints":[],"associated":[{"id":"34e1c812-3c3e-48c8-816d-467f7acd5cb9","name":"How mayny traversal orders are their in Binary Tree?","slug":"how-mayny-traversal-orders-are-their-in-binary-tree","type":4},{"id":"89830c2e-4697-4767-8d21-0a0e3a75128d","name":"Do binary tree have more then 2 children?","slug":"do-binary-tree-have-more-then-2-children","type":4},{"id":"e8acb453-daf6-49ad-a338-5990c57200cf","name":"In which order will the work go on?","slug":"in-which-order-will-the-work-go-on","type":4},{"id":"e9173585-f91c-42c7-9dde-edee0ed70f79","name":"What will be the base case here?","slug":"what-will-be-the-base-case-here","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":"04cc08c6-5137-43c2-8300-13379999c3c5","name":"Transform To Left-cloned Tree","slug":"transform-to-left-cloned-tree","type":1}],"next":{"id":"1a1cea30-6e50-4619-b1f4-631cfd5763ec","name":"Transform to Left Cloned Tree","type":3,"slug":"transform-to-left-cloned-tree"},"prev":{"id":"31a390f5-774e-4837-8e2d-c5ac99d34fd5","name":"Path to Leaf From Root in Range","type":3,"slug":"path-to-leaf-from-root-in-range"}}}
plane

Editor

Loading...

Transform To Left-cloned Tree

easy

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of createLeftCloneTree function. The function is expected to create a new node for every node equal in value to it and inserted between itself and it's left child. Check question video for clarity. 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

15 50 25 12 n n 37 n n 75 62 n n 87 n n

Sample Output

50

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode