{"id":"ed22aa32-9a95-4689-935f-03738e9dd746","name":"Burning Tree 2","description":"1. Given a binary tree and target. \r\n2. Find the minimum time required to burn the complete binary tree if the target is set on fire. \r\n3. It is known that in 1 second all nodes connected to a given node get burned. That is, its left child, right child and parent.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"1. The number of nodes in the tree is in the range [1, 10000].\r\n2. -1000 &lt;= Node.val &lt;= 1000\r\n3. All the values Node.val are unique.\r\n4. target is the value of one of the nodes in the tree.\r\n","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static ArrayList<ArrayList<Integer>> burningTree(TreeNode root, int data) {\r\n\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static TreeNode createTree(int[] arr, int[] IDX) {\r\n if (IDX[0] > arr.length || arr[IDX[0]] == -1) {\r\n IDX[0]++;\r\n return null;\r\n }\r\n TreeNode Treenode = new TreeNode(arr[IDX[0]++]);\r\n Treenode.left = createTree(arr, IDX);\r\n Treenode.right = createTree(arr, IDX);\r\n\r\n return Treenode;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++)\r\n arr[i] = scn.nextInt();\r\n\r\n int[] IDX = new int[1];\r\n TreeNode root = createTree(arr, IDX);\r\n int fireNode = scn.nextInt();\r\n\r\n ArrayList<ArrayList<Integer>> ans = burningTree(root, fireNode);\r\n if (ans.size() == 0)\r\n System.out.println();\r\n for (ArrayList<Integer> ar : ans) {\r\n for (Integer ele : ar)\r\n System.out.print(ele + \" \");\r\n System.out.println();\r\n }\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"15\r\n4\r\n2\r\n1\r\n-1\r\n-1\r\n3\r\n-1\r\n-1\r\n6\r\n5\r\n-1\r\n-1\r\n7\r\n-1\r\n-1\r\n2","sampleOutput":"2 \r\n1 3 4 \r\n6 \r\n5 7 \r\n","questionVideo":"","hints":[],"associated":[],"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":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"c8d5fa38-0401-47c3-bc59-3de7cfbc516a","name":"Burning Tree 2","slug":"burning-tree-2","type":1}],"next":{"id":"8f12e991-eec9-4b3c-bfb8-518bee537dfa","name":"Burning Tree 2","type":3,"slug":"burning-tree-2"},"prev":{"id":"467a9ce2-8324-47bb-8537-e867a409b2ed","name":"Burning Tree","type":3,"slug":"burning-tree"}}}

Burning Tree 2

1. Given a binary tree and target. 2. Find the minimum time required to burn the complete binary tree if the target is set on fire. 3. It is known that in 1 second all nodes connected to a given node get burned. That is, its left child, right child and parent.

{"id":"ed22aa32-9a95-4689-935f-03738e9dd746","name":"Burning Tree 2","description":"1. Given a binary tree and target. \r\n2. Find the minimum time required to burn the complete binary tree if the target is set on fire. \r\n3. It is known that in 1 second all nodes connected to a given node get burned. That is, its left child, right child and parent.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"1. The number of nodes in the tree is in the range [1, 10000].\r\n2. -1000 &lt;= Node.val &lt;= 1000\r\n3. All the values Node.val are unique.\r\n4. target is the value of one of the nodes in the tree.\r\n","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static ArrayList<ArrayList<Integer>> burningTree(TreeNode root, int data) {\r\n\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static TreeNode createTree(int[] arr, int[] IDX) {\r\n if (IDX[0] > arr.length || arr[IDX[0]] == -1) {\r\n IDX[0]++;\r\n return null;\r\n }\r\n TreeNode Treenode = new TreeNode(arr[IDX[0]++]);\r\n Treenode.left = createTree(arr, IDX);\r\n Treenode.right = createTree(arr, IDX);\r\n\r\n return Treenode;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++)\r\n arr[i] = scn.nextInt();\r\n\r\n int[] IDX = new int[1];\r\n TreeNode root = createTree(arr, IDX);\r\n int fireNode = scn.nextInt();\r\n\r\n ArrayList<ArrayList<Integer>> ans = burningTree(root, fireNode);\r\n if (ans.size() == 0)\r\n System.out.println();\r\n for (ArrayList<Integer> ar : ans) {\r\n for (Integer ele : ar)\r\n System.out.print(ele + \" \");\r\n System.out.println();\r\n }\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"15\r\n4\r\n2\r\n1\r\n-1\r\n-1\r\n3\r\n-1\r\n-1\r\n6\r\n5\r\n-1\r\n-1\r\n7\r\n-1\r\n-1\r\n2","sampleOutput":"2 \r\n1 3 4 \r\n6 \r\n5 7 \r\n","questionVideo":"","hints":[],"associated":[],"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":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"c8d5fa38-0401-47c3-bc59-3de7cfbc516a","name":"Burning Tree 2","slug":"burning-tree-2","type":1}],"next":{"id":"8f12e991-eec9-4b3c-bfb8-518bee537dfa","name":"Burning Tree 2","type":3,"slug":"burning-tree-2"},"prev":{"id":"467a9ce2-8324-47bb-8537-e867a409b2ed","name":"Burning Tree","type":3,"slug":"burning-tree"}}}
plane

Editor


Loading...

Burning Tree 2

medium

1. Given a binary tree and target. 2. Find the minimum time required to burn the complete binary tree if the target is set on fire. 3. It is known that in 1 second all nodes connected to a given node get burned. That is, its left child, right child and parent.

Constraints

1. The number of nodes in the tree is in the range [1, 10000]. 2. -1000 <= Node.val <= 1000 3. All the values Node.val are unique. 4. target is the value of one of the nodes in the tree.

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

15 4 2 1 -1 -1 3 -1 -1 6 5 -1 -1 7 -1 -1 2

Sample Output

2 1 3 4 6 5 7

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode