Just tried to solve this leetcode problem of even-odd tree. Leetcode description problem says:
To check if a given binary tree is an even-odd tree, we need to go through each node of the tree. This tree traversal can be DFS or BFS. We will go through both approaches here.
DFS: This traversal can be in-order/pre-order/post-order. As we know the root value, let’s check the root value with the above-mentioned conditions, then proceed to children nodes. So basically node value should not be odd in odd-indexed levels and should not be even in even-indexed levels. The next condition is strictly increasing order in even-indexed levels and strictly decreasing order in odd-indexed levels. This can be checked by saving the last traversed node in each level.
Below is the simple solution with DFS approach:
BFS: This is bread first search approach, where we will go through a set of nodes of one level at a time. In this approach, we will use queue to save the set of nodes of one level at a time.
Below is the BFS solution:
The observation is BFS solution is much faster than the DFS solution.
