During the coding interviews, problems based on binary search trees are one of the most frequently asked. So if you are preparing for an interview, you want to pay attention to the binary tree problems.

A binary tree is one type of data structure that stores the data in a hierarchical structure, which resembles a tree. A binary tree is a non-linear data structure that has many applications. To learn more about binary trees in general, check out the link.

This blog will discuss one of the popular problems based on binary trees. The problem is known as the even-odd tree.

Problem Statement

Let's discuss the problem statement before we learn its implementation.

An even-odd tree is a tree in which all the nodes at the even level are even, are all the nodes at the odd level are odd. Our task is to find out the whether the given binary tree is an even-odd tree or not.

Example 1

Input

In this tree:

One node has an even value at level 0(even level).

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

Four nodes have an even value at level 2(even level).

Output

Given Tree is an Even-Odd Binary Tree

Example 2

Input

In this tree:

One node has an even value at level 0(even level).

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

Three nodes have an even, and one node has an odd value at level 2(even level).

Output

Given Tree is not an Even-Odd Binary Tree

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach

Let's discuss the approach to the problem. As you may have observed from the problem statement, we must traverse nodes level by level. We need to iterate through the level by level to ensure the nodes are not violating the conditions for the even-odd tree.

We will use the level-order traversal or Breadth-first search to implement this approach. And each traversal of a particular level, we will check if the current nodes satisfy the conditions for the even-odd tree. If at any point we find out that node is violating the condition and that binary tree is not an even-odd tree.

The given tree is an even-odd tree if we do not find any invalid node based on the problem conditions.

Algorithm

Create a node with data and the address of the left and right nodes as values.

Enter the values in nodes to create a binary tree.

Pass the root node as the parameter to the evenOddtree() function to check whether the given tree is even-odd.

In the function, initialize a queue to perform the level-order traversing and a variable currentlevel = 0 to keep check of the current level of the tree.

Push the root node in the queue and check whether the value of the root node is even or not.

If it is even, continue and push the left and right nodes of the current node in the queue.

Repeat this process until we traverse all the tree nodes.

Return true if the given binary tree satisfies the conditions; return false.

DRY Run

C++ Implementation

#include<bits/stdc++.h>
using namespace std;
class node {
public: int data;
node * left;
node * right;
// Creating nodes.
node(int val) {
this -> data = val;
this -> left = NULL;
this -> right = NULL;
}
};
// Function to check if given tree is even-odd or not.
bool evenOddtree(node * root) {
if (root == NULL) {
return false;
}
// Intializing a queque
queue < node * > que;
int currentlevel = 0;
// Pushing root node in queque.
que.push(root);
// Checking the even-odd tree conditions until all nodes are traversed.
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
node * current = que.front();
int currentvalue = current -> data;
if (currentlevel % 2 == 0) {
if (currentvalue % 2 != 0) return 0;
} else {
if (currentvalue % 2 == 0) return 0;
}
que.pop();
if (current -> left != NULL) que.push(current -> left);
if (current -> right != NULL) que.push(current -> right);
}
// Incrementing the level.
currentlevel++;
}
return true;
}
int main() {
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);
bool result = evenOddtree(root);
if (result) {
cout << "Given Tree is an Even-Odd Binary Tree" << endl;
} else {
cout << "Given Tree is not an Even-Odd Binary Tree" << endl;
}
return 0;
}

Output

Python Implementation

class Node:
def __init__(self, data):
self.left = None
self.right = None
self.val = data
def newNode(data):
tempnode = Node(data)
return tempnode
# Function to check the even-odd binary tree.
def evenOddTree(root):
# Checking is tree ie empty.
if (root == None):
return True
# Intializing the queque
que = []
# Adding the root node in queque.
que.append(root)
currentlevel = 0
# Checking the even-odd conditions until are nodes are traversed.
while (que):
size = len(que)
for i in range(0,size):
node = que[0]
if (currentlevel % 2 == 0):
if (node.val % 2 != 0):
return False
else:
if (node.val % 2 == 0):
return False
que.pop(0)
if (node.left):
que.append(node.left)
if (node.right):
que.append(node.right)
# Incrementing the level of tree.
currentlevel += 1
return True
# Driver code
if __name__=="__main__":
root = None
root = newNode(0)
root.left = newNode(3)
root.right = newNode(5)
root.left.left = newNode(2)
root.left.right = newNode(4)
root.right.left = newNode(6)
root.right.right = newNode(2)
if (evenOddTree(root)):
print("Given Tree is an Even-Odd Binary Tree")
else:
print("Given Tree is not an Even-Odd Binary Tree")

Output

Complexity Analysis

The time complexity will be O(N), where ‘N’ is the number of nodes in the binary tree.

The space complexity will be O(N), where ‘N’ is the number of nodes in the binary tree.

Frequently Asked Questions

What is a root node?

The topmost node in the binary tree data structure that has no parent node is known as the root node.

What does traversing means?

Traversing means visiting nodes on a tree and displaying their data in a particular order.

How many types of traversal are there in the Binary search tree?

There are three types of traversals preorder, inorder, and postorder traversal.

Why do we use binary trees?

A binary tree is a data structure mainly used for searching and sorting data. In a binary tree, we store the data hierarchically.

What is the maximum number of nodes a parent node can have in a binary search tree?

In a binary search tree, a node can have a maximum of two nodes as children nodes.

Conclusion

In this blog, we learned how to check whether a binary tree is an even-odd tree. We have implemented the problem in C++ and python programming languages.

For more Tree data structure articles, you can refer following links: