Check if a Binary Tree is an Even-Odd Tree or Not

Riya
Last Updated: May 13, 2022

Introduction-  

This blog will discuss the problem "Check if a binary tree is an even-odd tree or not". In this problem, we will have a binary tree with 'N' nodes, each vertex will have a value associated with it, and we have to check if a binary tree is an even-odd tree or not for the given binary tree.

Before proceeding further, let's see what an even-odd binary tree is.


"A binary tree is said to be an even-odd binary tree if all the nodes at an even level in the tree have even values and all the nodes at an odd level in the tree have odd values."

 

Let's take an example to understand the problem:

Assume we have a given binary tree as shown below:

 


In this tree:

At level 0(even level), there is one node having an even value.

At level 1(odd level),  there are two nodes, each having an odd value

At level 2(even level), there are four nodes, each having an even value

Here, we can see that all the nodes at an even level have even values and all at an odd level have odd values. So, this binary tree is an even-odd binary tree.

Method 1 - Solution Approach

The approach to check if a binary tree is an even-odd tree or not is based on the level-order traversal of the binary tree. Initialize a variable to keep track of the level number and do the level order traversal of the given binary tree. For each level, check if the level is odd or even. Then check if a level is odd and any of the node's value is even or if the level is even and any of the node's value is odd, then return false. Finally, after traversing all the levels, return true if any of such cases are not found.

Algorithm -

 

Step 1. Create a class "Node" for creating the binary tree

Step 2. Create a function "checkForEvenOddBinaryTree()" to check if a binary tree is an even-odd tree or not, which takes a pointer to the tree's root node and returns true if the binary tree is an even-odd tree, else return false.

Step 3.  Create a queue to store the current level nodes and a variable "curr_level" to keep track of the current level number. Push the root node into the queue and keep "curr_level=0".

Step 4.  Traverse through all the levels of the queue. While traversing a level, check if it is an even level and any of the node's value is odd, return false. Similarly, if it is an odd level and any of the node's value is even, return false.

Step 5. Finally, after traversing all the levels, return true when the queue becomes empty. 

C++ code:

// C++ program to check if a binary tree is an even-odd tree or not
#include<bits/stdc++.h>
using namespace std;


class Node
{
public:
int val;
Node *left, *right;
Node(int val)
{
  this->val = val;
  this->left = NULL;
  this->right = NULL;
}
};


// Function to check if a binary tree is an even-odd tree or not
bool checkForEvenOddBinaryTree(Node *root)
{
if (root == NULL) {
return true;
}


// Creating a queue for level order traversal of the binary tree
queue<Node*> q;

// Inserting the root node
q.push(root);

// Variable to store the current level number
int curr_level = 0;


// Level order traversal
while (!q.empty())
{

// Variable to store the number of nodes in the current level
int curr_level_nodes = q.size();


for(int i = 0; i < curr_level_nodes; i++)
{
Node *curr_node = q.front();

// If the current level is even
if (curr_level % 2 == 0)
{

// If the node value is odd, return false 
if (curr_node->val % 2 == 1) {
return false;
}
}

// If the current level is odd
else if (curr_level % 2 == 1)
{

// If the node value is even, return false
if (curr_node->val % 2 == 0) {
return true;
}
}

// Push the nodes of the next level into the queue
if (curr_node->left != NULL)
{
q.push(curr_node->left);
}
if (curr_node->right != NULL)
{
q.push(curr_node->right);
}
}


// Increase the level number by one
curr_level++;
}
return true;
}


int main()
{

// Construct a Binary Tree
Node *root = NULL;
root = new Node(0);
root->left = new Node(3);
root->right = new Node(5);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(8);


// Call the function to check if a binary tree is an even-odd tree or not
if (checkForEvenOddBinaryTree(root)) {
cout << "Yes, the given binary tree is an even-odd tree";
}
else {
cout << "No, the given binary tree is not an even-odd tree";
}
}
Output:
Yes, the given binary tree is an even-odd tree

Algorithm Complexity: 

Time Complexity: O(N)

In the function "checkForEvenOddBinaryTree()" to check if a binary tree is an even-odd tree or not, we have traversed through all the nodes of the binary tree. So, the time complexity is O(N), where 'N' is the number of nodes in the given binary tree.

Space Complexity: O(N) 

In the function "checkForEvenOddBinaryTree()" to check if a binary tree is an even-odd tree or not, we have created a queue to store the tree's nodes. So the space complexity is O(N), where 'N' is the number of nodes in the given binary tree.

Method 2 - Solution Approach

This is a recursive approach to check if a binary tree is an even-odd tree or not. First, check the root node's value, as it is an even level; if the root node's value is odd, then return false. And if the root node's value is even, create a recursive function to check for other levels of the given binary tree.

We can notice that if a node is at an even level, its children must be on the odd level and vice versa. And if a tree is an even-odd tree, then the node's value at the even level will be even, and the node's value at an odd level will be odd. We know that the difference between an even number and an odd number is always an odd number. So, the difference between the value of a node and its child must be an odd number in the case of an even-odd tree.

So, this is the intuition behind this approach, recursively check for each node and if for any node, it is found that the difference between the value of the node and its child is even, then return false. And, if for all nodes, the difference between the value of the node and its child is odd, then it is an even-odd tree. Please note here that we have separately checked for level- 0, i.e., for the tree's root node, before calling the recursive function.

Algorithm -

 

Step 1. Create a class "Node" for creating the binary tree

Step 2. Create a function "checkForEvenOddBinaryTree()" to check if a binary tree is an even-odd tree or not, which takes a pointer to the tree's root node and returns true if the binary tree is an even-odd tree, else return false. First, check for the root node value; if it is odd, return false. Else, call the recursive function to check for the next levels of the binary tree.

Step 3.  Create the recursive function "isEvenOddRec()", which takes the pointer to a binary tree node. If its left child and right child exist and the difference between the current node's value and its child is even, then return false. Then, recursively call this function for its left and right child.

Step 4.  If the recursive function returns true for both left and right children of the tree, return true, else return false.

C++ code:

// C++ program to check if a binary tree is an even-odd tree or not
#include <bits/stdc++.h>
using namespace std;


class Node
{
public:
int val;
Node *left, *right;
Node(int val)
{
  this->val = val;
  this->left = NULL;
  this->right = NULL;
}
};


// Recursive Function to recursively traverse tree and check if a binary tree is an even-odd tree
bool isEvenOddRec(Node * node){

// Base Case
if(node==NULL) {
return true;
}

// If left node exists, check for it
if(node->left!=NULL && abs(node->val - node->left->val)%2==0) {
return false;
}

// f right node exists, check for it
if(node->right!=NULL && abs(node->val - node->right->val)%2==0) {
return false;
}

// Call the function recursively for the left and right child 
return isEvenOddRec(node->left) && isEvenOddRec(node->right);
}


// Function to check if binary tree is an even-odd binary tree
bool checkForEvenOddBinaryTree(Node * root)
{

// If tree is NULL then it will be an even-odd tree, so return true
if(root==NULL) {
return true;
}

// Root node is at even level so if root node value is odd return false
if(root->val%2 != 0) {
return false;
}

// Call the recursive function to check if a binary tree is an even-odd tree
return isEvenOddRec(root);
}


// driver program
int main()
{

// Construct a Binary Tree
Node *root = NULL;
root = new Node(0);
root->left = new Node(3);
root->right = new Node(5);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(8);

// Call the function to check if a binary tree is an even-odd tree or not
if (checkForEvenOddBinaryTree(root)) {
cout << "Yes, the given binary tree is an even-odd tree";
}
else {
cout << "No, the given binary tree is not an even-odd tree";
}
}
Output:
Yes, the given binary tree is an even-odd treeAlgorithm Complexity: 

 

Time Complexity: O(N)

The recursive function "isEvenOddRec()" is recursively called for each node of the tree, and for each node, it takes O(1) time. So, the time complexity is O(N), where 'N' is the number of nodes in the given binary tree.

Space Complexity: O(1) 

We have used constant space, so the space complexity is O(1).

Frequently asked questions-

  1. What is the level order traversal of a tree?

Level OrderTraversal is a breadth-first traversal of a tree in which we traverse the tree level-wise. In this, we first cover all the nodes of a present level then move to the next level of the tree.

2.  Why do we use a queue in a level order traversal of a tree?

In level order traversal, we need to traverse the nodes in an order in which they are stored, i.e., while traversing the current level of the tree, we store the children of these nodes, and we need to process those children nodes in an order in which they are stored. That's why we use a 'queue' data structure as it is a "First In First Out" type of data structure.

 

Key takeaways-

This article discussed the problem "Check if a binary tree is an even-odd tree or not", two approaches to solve this problem, their C++ implementation, and their time and space complexity. If you want to solve tree data structure problems for practice, you can visit codestudio.


If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

 

Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
1 upvote