A binary tree is named Even-Odd if it meets the following conditions:
0, its children are at level index 1, their children are at level index 2, etc.Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.
Example 1:
Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2] Output: true Explanation: The node values on each level are: Level 0: [1] Level 1: [10,4] Level 2: [3,7,9] Level 3: [12,8,6,2] Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.
Example 2:
Input: root = [5,4,2,3,3,7] Output: false Explanation: The node values on each level are: Level 0: [5] Level 1: [4,2] Level 2: [3,3,7] Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.
Example 3:
Input: root = [5,9,1,3,5,7] Output: false Explanation: Node values in the level 1 should be even integers.
Constraints:
[1, 105].1 <= Node.val <= 106This approach employs a breadth-first search (BFS) to traverse the binary tree level by level. We maintain a queue to keep track of the nodes at each level, examining their values to ensure compliance with the Even-Odd criteria:
The solution employs a queue for level-order traversal. On each level, it examines the nodes' values to ensure conformity with the problem's even-odd level requirements.
JavaScript
Time Complexity: O(N), where N is the number of nodes, as each node is inspected once.
Space Complexity: O(M), where M is the maximum number of nodes at any level in the tree (width of the tree), due to the BFS queue.
This approach applies a depth-first search (DFS) method, maintaining level information to confirm constraints. We use recursion to explore the tree, while an array stores the last value seen on each level to validate order constraints.
In the C++ solution, we use a recursive function to perform DFS while maintaining the last meaningful value for level validation in an array. This array ensures all nodes at each level meet the Even-Odd Tree constraints.
Java
Time Complexity: O(N), with N being the number of nodes.
Space Complexity: O(H), where H is the height of the tree, accounting for recursion stack and the array storing last values at each level.
| Approach | Complexity |
|---|---|
| Level Order Traversal (BFS) | Time Complexity: O(N), where N is the number of nodes, as each node is inspected once. |
| Depth First Search (DFS) with Level Tracking | Time Complexity: O(N), with N being the number of nodes. |
Even Odd Tree - Leetcode 1609 - Python • NeetCodeIO • 14,295 views views
Watch 9 more video solutions →Practice Even Odd Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor