{"id":"723ff488-fdc0-429d-94d7-68cea90b4984","name":"Longest Zigzag Path In A Binary Tree","description":"1. You are given a partially written function to solve.\r\n2. Given a binary tree root, a ZigZag path for a binary tree is defined as follow:\r\n a. Choose any node in the binary tree and a direction (right or left).\r\n b. If the current direction is right then move to the right child of the current node otherwise move to the left child.\r\n c. Change the direction from right to left or right to left.\r\n d. Repeat the second and third step until you can't move in the tree.\r\n\r\n3.Zigzag length is defined in terms of edges. (A single node has a length of 0).\r\n4. Return the longest ZigZag path contained in that tree.","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\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\nint longestZigZagPath(TreeNode *root)\r\n{\r\n return 0;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1){\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 cout << longestZigZagPath(root) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\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 longestZigZagPath(TreeNode root) {\r\n return 0;\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 System.out.println(longestZigZagPath(root));\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":"4\r\n","questionVideo":"https://www.youtube.com/embed/7aqHhENUbkQ","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":"c4909c9a-dc89-409e-979b-ad0f47400ca9","name":"Longest Zigzag Path In A Binary Tree","slug":"longest-zigzag-path-in-a-binary-tree","type":1}],"next":{"id":"9db2bf06-accb-4799-886e-8e6f06868f9b","name":"Longest ZigZag Path in a binary Tree","type":3,"slug":"longest-zigzag-path-in-a-binary-tree"},"prev":{"id":"043fdc90-3893-47dc-820e-a6ceba45e435","name":"Construct Bst From Postorder Traversal","type":0,"slug":"construct-bst-from-postorder-traversal"}}}

Longest Zigzag Path In A Binary Tree

1. You are given a partially written function to solve. 2. Given a binary tree root, a ZigZag path for a binary tree is defined as follow: a. Choose any node in the binary tree and a direction (right or left). b. If the current direction is right then move to the right child of the current node otherwise move to the left child. c. Change the direction from right to left or right to left. d. Repeat the second and third step until you can't move in the tree. 3.Zigzag length is defined in terms of edges. (A single node has a length of 0). 4. Return the longest ZigZag path contained in that tree.

{"id":"723ff488-fdc0-429d-94d7-68cea90b4984","name":"Longest Zigzag Path In A Binary Tree","description":"1. You are given a partially written function to solve.\r\n2. Given a binary tree root, a ZigZag path for a binary tree is defined as follow:\r\n a. Choose any node in the binary tree and a direction (right or left).\r\n b. If the current direction is right then move to the right child of the current node otherwise move to the left child.\r\n c. Change the direction from right to left or right to left.\r\n d. Repeat the second and third step until you can't move in the tree.\r\n\r\n3.Zigzag length is defined in terms of edges. (A single node has a length of 0).\r\n4. Return the longest ZigZag path contained in that tree.","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\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\nint longestZigZagPath(TreeNode *root)\r\n{\r\n return 0;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1){\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 cout << longestZigZagPath(root) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\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 longestZigZagPath(TreeNode root) {\r\n return 0;\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 System.out.println(longestZigZagPath(root));\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":"4\r\n","questionVideo":"https://www.youtube.com/embed/7aqHhENUbkQ","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":"c4909c9a-dc89-409e-979b-ad0f47400ca9","name":"Longest Zigzag Path In A Binary Tree","slug":"longest-zigzag-path-in-a-binary-tree","type":1}],"next":{"id":"9db2bf06-accb-4799-886e-8e6f06868f9b","name":"Longest ZigZag Path in a binary Tree","type":3,"slug":"longest-zigzag-path-in-a-binary-tree"},"prev":{"id":"043fdc90-3893-47dc-820e-a6ceba45e435","name":"Construct Bst From Postorder Traversal","type":0,"slug":"construct-bst-from-postorder-traversal"}}}
plane

Editor

Loading...

Longest Zigzag Path In A Binary Tree

easy

1. You are given a partially written function to solve. 2. Given a binary tree root, a ZigZag path for a binary tree is defined as follow: a. Choose any node in the binary tree and a direction (right or left). b. If the current direction is right then move to the right child of the current node otherwise move to the left child. c. Change the direction from right to left or right to left. d. Repeat the second and third step until you can't move in the tree. 3.Zigzag length is defined in terms of edges. (A single node has a length of 0). 4. Return the longest ZigZag path contained in that tree.

Constraints

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

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

4

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode