{"id":"6a195594-29d7-4b22-a67a-80013af26ed0","name":"Maximum Width Of Binary Tree","description":"1. Given the root of a binary tree, return the maximum width of the given tree.\r\n2. The maximum width of a tree is the maximum width among all levels.\r\n3. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you. ","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 <bits/stdc++.h>\nusing namespace std;\n\nclass TreeNode\n{\npublic:\n int val = 0;\n TreeNode* left = nullptr;\n TreeNode* right = nullptr;\n\n TreeNode(int val)\n {\n this->val = val;\n }\n};\n\nint widthOfBinaryTree(TreeNode* root)\n{\n}\n\n// input_Section_====================================================================\n\nvoid display(TreeNode* node)\n{\n if (node == nullptr)\n return;\n\n string str = \"\";\n str += ((node->left != nullptr ? to_string(node->left->val) : \".\"));\n str += (\" -> \" + to_string(node->val) + \" <- \");\n str += ((node->right != nullptr ? to_string(node->right->val) : \".\"));\n\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\nint idx = 0;\nTreeNode* deserialize(vector<string>& arr)\n{\n if (idx >= arr.size() || arr[idx].compare(\"null\") == 0)\n {\n idx++;\n return nullptr;\n }\n\n TreeNode* node = new TreeNode(stoi(arr[idx++]));\n node->left = deserialize(arr);\n node->right = deserialize(arr);\n\n return node;\n}\n\nTreeNode* deserialize(string s)\n{\n stringstream ss(s);\n string word;\n vector<string> arr;\n while (ss >> word)\n {\n arr.push_back(word);\n }\n return deserialize(arr);\n}\n\nvoid solve()\n{\n string s;\n cin >> s;\n TreeNode* root = deserialize(s);\n\n cout << widthOfBinaryTree(root) << endl;\n}\n\nint main()\n{\n solve();\n return 0;\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 int widthOfBinaryTree(TreeNode root) {\r\n\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(TreeNode node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append((node.left != null ? node.left.val : \".\"));\r\n sb.append(\" -> \" + node.val + \" <- \");\r\n sb.append((node.right != null ? node.right.val : \".\"));\r\n\r\n System.out.println(sb.toString());\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static int idx = 0;\r\n\r\n private static TreeNode deserialize(String[] arr) {\r\n if (idx >= arr.length || arr[idx].equals(\"null\")) {\r\n idx++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(Integer.parseInt(arr[idx++]));\r\n node.left = deserialize(arr);\r\n node.right = deserialize(arr);\r\n\r\n return node;\r\n }\r\n\r\n public static TreeNode deserialize(String str) {\r\n String[] arr = str.split(\" \");\r\n return deserialize(arr);\r\n }\r\n\r\n public static void solve() {\r\n String str = scn.nextLine();\r\n TreeNode root = deserialize(str);\r\n\r\n int ans = widthOfBinaryTree(root);\r\n System.out.println(ans);\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":"1 3 5 null null 3 null null 2 null 9 null null","sampleOutput":"4\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":"e91d2bb9-2ec5-40ec-809e-22a60e551266","name":"Maximum Width Of Binary Tree","slug":"maximum-width-of-binary-tree","type":1}],"next":{"id":"82f878f9-c02d-4e46-938a-470af9990577","name":"Maximum Width Of Binary Tree","type":3,"slug":"maximum-width-of-binary-tree"},"prev":{"id":"3ed3f627-a1dd-4b9b-858d-e8dd63505e7f","name":"All Nodes Distance K In Binary Tree","type":0,"slug":"all-nodes-distance-k-in-binary-tree"}}}

Maximum Width Of Binary Tree

1. Given the root of a binary tree, return the maximum width of the given tree. 2. The maximum width of a tree is the maximum width among all levels. 3. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

{"id":"6a195594-29d7-4b22-a67a-80013af26ed0","name":"Maximum Width Of Binary Tree","description":"1. Given the root of a binary tree, return the maximum width of the given tree.\r\n2. The maximum width of a tree is the maximum width among all levels.\r\n3. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you. ","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 <bits/stdc++.h>\nusing namespace std;\n\nclass TreeNode\n{\npublic:\n int val = 0;\n TreeNode* left = nullptr;\n TreeNode* right = nullptr;\n\n TreeNode(int val)\n {\n this->val = val;\n }\n};\n\nint widthOfBinaryTree(TreeNode* root)\n{\n}\n\n// input_Section_====================================================================\n\nvoid display(TreeNode* node)\n{\n if (node == nullptr)\n return;\n\n string str = \"\";\n str += ((node->left != nullptr ? to_string(node->left->val) : \".\"));\n str += (\" -> \" + to_string(node->val) + \" <- \");\n str += ((node->right != nullptr ? to_string(node->right->val) : \".\"));\n\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\nint idx = 0;\nTreeNode* deserialize(vector<string>& arr)\n{\n if (idx >= arr.size() || arr[idx].compare(\"null\") == 0)\n {\n idx++;\n return nullptr;\n }\n\n TreeNode* node = new TreeNode(stoi(arr[idx++]));\n node->left = deserialize(arr);\n node->right = deserialize(arr);\n\n return node;\n}\n\nTreeNode* deserialize(string s)\n{\n stringstream ss(s);\n string word;\n vector<string> arr;\n while (ss >> word)\n {\n arr.push_back(word);\n }\n return deserialize(arr);\n}\n\nvoid solve()\n{\n string s;\n cin >> s;\n TreeNode* root = deserialize(s);\n\n cout << widthOfBinaryTree(root) << endl;\n}\n\nint main()\n{\n solve();\n return 0;\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 int widthOfBinaryTree(TreeNode root) {\r\n\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(TreeNode node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append((node.left != null ? node.left.val : \".\"));\r\n sb.append(\" -> \" + node.val + \" <- \");\r\n sb.append((node.right != null ? node.right.val : \".\"));\r\n\r\n System.out.println(sb.toString());\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static int idx = 0;\r\n\r\n private static TreeNode deserialize(String[] arr) {\r\n if (idx >= arr.length || arr[idx].equals(\"null\")) {\r\n idx++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(Integer.parseInt(arr[idx++]));\r\n node.left = deserialize(arr);\r\n node.right = deserialize(arr);\r\n\r\n return node;\r\n }\r\n\r\n public static TreeNode deserialize(String str) {\r\n String[] arr = str.split(\" \");\r\n return deserialize(arr);\r\n }\r\n\r\n public static void solve() {\r\n String str = scn.nextLine();\r\n TreeNode root = deserialize(str);\r\n\r\n int ans = widthOfBinaryTree(root);\r\n System.out.println(ans);\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":"1 3 5 null null 3 null null 2 null 9 null null","sampleOutput":"4\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":"e91d2bb9-2ec5-40ec-809e-22a60e551266","name":"Maximum Width Of Binary Tree","slug":"maximum-width-of-binary-tree","type":1}],"next":{"id":"82f878f9-c02d-4e46-938a-470af9990577","name":"Maximum Width Of Binary Tree","type":3,"slug":"maximum-width-of-binary-tree"},"prev":{"id":"3ed3f627-a1dd-4b9b-858d-e8dd63505e7f","name":"All Nodes Distance K In Binary Tree","type":0,"slug":"all-nodes-distance-k-in-binary-tree"}}}
plane

Editor


Loading...

Maximum Width Of Binary Tree

medium

1. Given the root of a binary tree, return the maximum width of the given tree. 2. The maximum width of a tree is the maximum width among all levels. 3. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

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

1 3 5 null null 3 null null 2 null 9 null null

Sample Output

4

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode