{"id":"6760acf8-0ffb-4d26-b92c-d3a1470b2070","name":"Vertical Order Traversal Of A Binarytree-ii","description":"1. Given a Binary Tree, print Vertical Order of it. \r\n2. For each node at position (row, col), its left and right \r\n children will be at positions (row + 1, col - 1) and (row + 1, col + 1) \r\n respectively. The root of the tree is at (0, 0).\r\n3. The vertical order traversal of a binary tree is a list of top-to-bottom \r\n orderings for each column index starting from the leftmost column and ending \r\n on the rightmost column. There may be multiple nodes in the same row and same \r\n column. In such a case, sort these nodes by their values.\r\n4. For More Information Watch Question Video link below.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^5\r\n-1000 &lt;= value of Node data &lt;= 1000\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n#include <queue>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode *left = nullptr;\r\n TreeNode *right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nvector<vector<int>> verticalOrderTraversal(TreeNode *root)\r\n{\r\n}\r\n\r\n// input_section=================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1)\r\n {\r\n IDX[0]++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode *node = new TreeNode(arr[IDX[0]++]);\r\n node->left = createTree(arr, IDX);\r\n node->right = createTree(arr, IDX);\r\n\r\n return node;\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> arr(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n\r\n vector<int> IDX(1, 0);\r\n TreeNode *root = createTree(arr, IDX);\r\n\r\n vector<vector<int>> ans = verticalOrderTraversal(root);\r\n int idx = 0;\r\n for (vector<int> &i : ans)\r\n {\r\n cout << idx++ << \" -> \";\r\n for (int j : i)\r\n {\r\n cout << j << \" \";\r\n }\r\n cout << endl;\r\n }\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"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>> verticalOrderTraversal(TreeNode root) {\r\n return null;\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 node = new TreeNode(arr[IDX[0]++]);\r\n node.left = createTree(arr, IDX);\r\n node.right = createTree(arr, IDX);\r\n\r\n return node;\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\r\n ArrayList<ArrayList<Integer>> ans = verticalOrderTraversal(root);\r\n int idx = 0;\r\n for (ArrayList<Integer> i : ans) {\r\n System.out.print(idx++ + \" -> \");\r\n for (Integer j : i)\r\n System.out.print(j + \" \");\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":"easy","sampleInput":"15\r\n1\r\n1\r\n-1\r\n1\r\n1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1","sampleOutput":"0 -> 1 1 \r\n1 -> 1 1 1 \r\n2 -> 1 1 \r\n","questionVideo":"https://www.youtube.com/embed/8o-0CxZHNdQ","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":"331ce8f6-acef-46b0-846a-34f3cde4475a","name":"Vertical Order Traversal Of A Binarytree-ii","slug":"vertical-order-traversal-of-a-binarytree-ii","type":1}],"next":{"id":"704c5aff-549f-4e67-8a86-53e9611805f2","name":"Vertical Order Traversal Of A Binarytree-ii","type":3,"slug":"vertical-order-traversal-of-a-binarytree-ii"},"prev":{"id":"32e50c06-dd4c-4a99-9928-14340f5be756","name":"Vertical Order Traversal Of A Binarytree","type":1,"slug":"vertical-order-traversal-of-a-binarytree"}}}

Vertical Order Traversal Of A Binarytree-ii

1. Given a Binary Tree, print Vertical Order of it. 2. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0). 3. The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. 4. For More Information Watch Question Video link below.

{"id":"6760acf8-0ffb-4d26-b92c-d3a1470b2070","name":"Vertical Order Traversal Of A Binarytree-ii","description":"1. Given a Binary Tree, print Vertical Order of it. \r\n2. For each node at position (row, col), its left and right \r\n children will be at positions (row + 1, col - 1) and (row + 1, col + 1) \r\n respectively. The root of the tree is at (0, 0).\r\n3. The vertical order traversal of a binary tree is a list of top-to-bottom \r\n orderings for each column index starting from the leftmost column and ending \r\n on the rightmost column. There may be multiple nodes in the same row and same \r\n column. In such a case, sort these nodes by their values.\r\n4. For More Information Watch Question Video link below.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^5\r\n-1000 &lt;= value of Node data &lt;= 1000\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n#include <queue>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode *left = nullptr;\r\n TreeNode *right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nvector<vector<int>> verticalOrderTraversal(TreeNode *root)\r\n{\r\n}\r\n\r\n// input_section=================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1)\r\n {\r\n IDX[0]++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode *node = new TreeNode(arr[IDX[0]++]);\r\n node->left = createTree(arr, IDX);\r\n node->right = createTree(arr, IDX);\r\n\r\n return node;\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> arr(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n\r\n vector<int> IDX(1, 0);\r\n TreeNode *root = createTree(arr, IDX);\r\n\r\n vector<vector<int>> ans = verticalOrderTraversal(root);\r\n int idx = 0;\r\n for (vector<int> &i : ans)\r\n {\r\n cout << idx++ << \" -> \";\r\n for (int j : i)\r\n {\r\n cout << j << \" \";\r\n }\r\n cout << endl;\r\n }\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"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>> verticalOrderTraversal(TreeNode root) {\r\n return null;\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 node = new TreeNode(arr[IDX[0]++]);\r\n node.left = createTree(arr, IDX);\r\n node.right = createTree(arr, IDX);\r\n\r\n return node;\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\r\n ArrayList<ArrayList<Integer>> ans = verticalOrderTraversal(root);\r\n int idx = 0;\r\n for (ArrayList<Integer> i : ans) {\r\n System.out.print(idx++ + \" -> \");\r\n for (Integer j : i)\r\n System.out.print(j + \" \");\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":"easy","sampleInput":"15\r\n1\r\n1\r\n-1\r\n1\r\n1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1","sampleOutput":"0 -> 1 1 \r\n1 -> 1 1 1 \r\n2 -> 1 1 \r\n","questionVideo":"https://www.youtube.com/embed/8o-0CxZHNdQ","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":"331ce8f6-acef-46b0-846a-34f3cde4475a","name":"Vertical Order Traversal Of A Binarytree-ii","slug":"vertical-order-traversal-of-a-binarytree-ii","type":1}],"next":{"id":"704c5aff-549f-4e67-8a86-53e9611805f2","name":"Vertical Order Traversal Of A Binarytree-ii","type":3,"slug":"vertical-order-traversal-of-a-binarytree-ii"},"prev":{"id":"32e50c06-dd4c-4a99-9928-14340f5be756","name":"Vertical Order Traversal Of A Binarytree","type":1,"slug":"vertical-order-traversal-of-a-binarytree"}}}
plane

Editor

Loading...

Vertical Order Traversal Of A Binarytree-ii

easy

1. Given a Binary Tree, print Vertical Order of it. 2. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0). 3. The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. 4. For More Information Watch Question Video link below.

Constraints

0 <= Number of Nodes <= 10^5 -1000 <= value of Node data <= 1000

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

15 1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1

Sample Output

0 -> 1 1 1 -> 1 1 1 2 -> 1 1

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode