How to Solve Even Odd Tree
Even Odd Tree Introduction
Even Odd Tree Introduction
The Even Odd Tree problem asks us to return true if each even level of the tree's values are increasing while all odd levels are decreasing otherwise return false. To solve this we can traverse the binary tree level by level, pass the root node into a queue and process each node in the queue during each iteration, we can check if the values of the nodes at the current level meet the requirements based on their level index.
Even Odd Tree Problem
Even Odd Tree Problem
Given a tree, verify that on even levels, all values in the level are strictly increasing and even. On odd levels, verify all values in the level are strictly decreasing and odd.
Example Inputs and Outputs
Example 1
Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: True
Example 2
Input: root = [5,4,2,3,3,7]
Output: False
Even Odd Tree Solutions
Even Odd Tree Solutions
To solve this problem, we can traverse the binary tree level by level and check if the nodes satisfy the conditions. We start at the root node and process each level one by one, making sure that the values meet the criteria set out by the problem.
We start by settting up a queue or a similar data structure (can use deque) to hold the nodes of each level. We add the root node to the queue and then proceed to process each node in the queue. During each iteration, we can check if the values of the nodes at the current level meet the requirements based on their level index. If any node invalidates the conditions in the problem, we then know that the binary tree is not an "Even-Odd" binary tree and return False.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isEvenOddTree(root):
if not root:
return False
queue = [root]
level_index = 0
while queue:
level_size = len(queue)
prev_val = None
next_level = []
for _ in range(level_size):
node = queue.pop(0)
val = node.val
if (level_index % 2 == 0 and (val % 2 != 1 or (prev_val is not None and val <= prev_val))) or \
(level_index % 2 != 0 and (val % 2 != 0 or (prev_val is not None and val >= prev_val))):
return False
prev_val = val
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
queue = next_level
level_index += 1
return True
# Driver code to test the function
# We'll create the following tree:
# 1
# / \
# 10 4
# / \ \
# 3 7 9
root = TreeNode(1)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(9)
print(isEvenOddTree(root)) # Output: True
# Our second tree:
# 5
# / \
# 4 2
# / \ /
# 3 3 7
root2 = TreeNode(5)
root2.left = TreeNode(4)
root2.right = TreeNode(2)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(3)
root2.right.left = TreeNode(7)
print(isEvenOddTree(root2)) # Output: False1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7
8def isEvenOddTree(root):
9 if not root:
10 return False
11
12 queue = [root]
13 level_index = 0
14
15 while queue:
16 level_size = len(queue)
17 prev_val = None
18 next_level = []
19
20 for _ in range(level_size):
21 node = queue.pop(0)
22 val = node.val
23
24 if (level_index % 2 == 0 and (val % 2 != 1 or (prev_val is not None and val <= prev_val))) or \
25 (level_index % 2 != 0 and (val % 2 != 0 or (prev_val is not None and val >= prev_val))):
26 return False
27
28 prev_val = val
29
30 if node.left:
31 next_level.append(node.left)
32 if node.right:
33 next_level.append(node.right)
34
35 queue = next_level
36 level_index += 1
37
38 return True
39
40
41# Driver code to test the function
42# We'll create the following tree:
43# 1
44# / \
45# 10 4
46# / \ \
47# 3 7 9
48root = TreeNode(1)
49root.left = TreeNode(10)
50root.right = TreeNode(4)
51root.left.left = TreeNode(3)
52root.left.right = TreeNode(7)
53root.right.right = TreeNode(9)
54
55print(isEvenOddTree(root)) # Output: True
56
57# Our second tree:
58# 5
59# / \
60# 4 2
61# / \ /
62# 3 3 7
63root2 = TreeNode(5)
64root2.left = TreeNode(4)
65root2.right = TreeNode(2)
66root2.left.left = TreeNode(3)
67root2.left.right = TreeNode(3)
68root2.right.left = TreeNode(7)
69
70print(isEvenOddTree(root2)) # Output: FalseTime/Space Complexity Analysis
- Time Complexity: O(N), where n is the total number of nodes in the binary tree as we visit each node once.
- Space Complexity: O(m), where m represents the maximum number of nodes at any level in the binary tree.
Note:
In this solution, the space is not dependant on the height of the tree as would be the case in a recursive solution
It is possible to achieve O(1) space complexity by checking parent and child absolutely difference
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
