Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example 1
2.2.
Example 2
3.
Approach
3.1.
Algorithm
3.2.
DRY Run
3.3.
C++ Implementation
3.4.
Python Implementation
3.5.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a root node?
4.2.
What does traversing means?
4.3.
How many types of traversal are there in the Binary search tree?
4.4.
Why do we use binary trees?
4.5.
What is the maximum number of nodes a parent node can have in a binary search tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

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.

introduction image

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

example image 1

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

example image 2

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

  1. Create a node with data and the address of the left and right nodes as values.
     
  2. Enter the values in nodes to create a binary tree.
     
  3. Pass the root node as the parameter to the evenOddtree() function to check whether the given tree is even-odd.
     
  4. 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.
     
  5. Push the root node in the queue and check whether the value of the root node is even or not.
     
  6. If it is even, continue and push the left and right nodes of the current node in the queue.
     
  7. Repeat this process until we traverse all the tree nodes.
     
  8. Return true if the given binary tree satisfies the conditions; return false.

DRY Run

dry run image
dry run image
dry run image

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

c++ code 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

python code 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:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Sum of Leaf Node at each Horizontal Level of Binary Tree
Next article
Difference between Sums of Odd Level and Even Level Nodes of a Binary Tree
Live masterclass