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
2.1.1.
Input
2.2.
Explanation
3.
Approach
4.
Algorithm
5.
Dry Run
5.1.
C++ implementation
5.1.1.
Main Function Parameter
5.1.2.
Output
5.2.
Java Implementation
5.2.1.
Main Function Parameter
5.2.2.
Output
6.
Complexities
6.1.
Time complexity
6.2.
Space Complexity
7.
Frequently asked questions
7.1.
What is the purpose of the algorithm?
7.2.
What is an Even-Odd Tree?
7.3.
How to find out if an array/vector is sorted in increasing?
7.4.
What is the difference between a binary tree and a binary search tree?
7.5.
What is the height of a binary tree?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Check if a binary tree contains node values are in strictly increasing and decreasing order at even and odd levels

Author Shreya Deep
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A Binary Tree is a Data Structure having a root node and, at most, two children nodes. Here in this article, we will be going to understand a very famous problem. This problem is related to the binary trees, which is already asked in many top companies like Facebook, Google and Microsoft.

Introduction

Problem Statement

Given a binary tree, write a function to determine if the node values are in a strictly increasing order for nodes at even levels and a strictly decreasing order for nodes at odd levels. Where we assume the root node is at 0 level.

Example

Input

Example

Output

True

Explanation

In the above example, level 0 is 2, and the number contained in odd level 1 is 8 and 3, which is strictly decreasing. As it satisfies the condition. 

Similarly, In even level 2, numbers are 5,7,9 and 10, which are in increasing order. It also satisfies the condition.

The last odd level 3 numbers are 9,3, and 1, which are in decreasing order. It also satisfies the condition. So the overall result is true.

Explanation
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

The approach to check if a binary tree contains node values in strictly increasing and decreasing order at even and odd levels:

  • Perform a level-order traversal of the binary tree, keeping track of the level of each node.
Approach
  • For each level, check if the node values are in strictly increasing order for even levels and strictly decreasing order for odd levels.
level and checks
  • If all levels satisfy the condition, return true. Otherwise, return false.

To implement this approach, we can use a queue data structure to perform the level-order traversal of the binary tree. We can keep track of the level of each node by adding an additional value to the tuple representing each node in the queue.

During the level-order traversal, we can keep track of the current level and the previous node value. For each level, we check if the node values are in strictly increasing order for even levels and strictly decreasing order for odd levels. If any level does not satisfy the condition, we can immediately return false.

Algorithm

Below is the algorithm:

  • Check if the root of the binary tree is null, and return true if so.
     
  • Initialise a queue with the root of the binary tree and variables to track the current level and the last value processed.
     
  • While the queue is not empty, dequeue the next node and add its value to a list of values for the current level.
     
  • Check if the value of the node is greater or smaller than the last value processed, depending on the level of the node. If the condition is violated, set the flag to false.
     
  • Enqueue the left and right child nodes of the current node if they exist.
     
  • Increment the level counter, and repeat the above steps for the next level.
     
  • Return the flag, which indicates if the binary tree satisfies the required conditions.

Dry Run

Consider the following binary tree:

binary tree

Starting at the root node with value 2, we perform a level-order traversal using a queue. We keep track of the current level of the tree and a flag indicating if the nodes in that level have values that satisfy the required conditions.
 

  • First, we add the root node to the queue and set the level to 0.
set the level to 0
  • While the queue is not empty, we process each node in the queue for the current level.
     
  • We check if the value of the node is even or odd depending on the level, and if it does not satisfy the condition, we set the flag to false.
even or odd depending on the level
  • We also check if the value of the node is greater than the value of the previous node in the current level in case of even level( To satisfy increasing order). If it is not, we set the flag to false.
     
  • Similarly, we will also check if the value of the node is smaller than the value of the previous node in the current level in case of odd level( To satisfy decreasing order). If it is not, we set the flag to false.
odd
even
  • If all nodes in the current level satisfy the conditions, we continue with the next level.
     
  • We repeat the above steps until we have processed all nodes in the tree.
     
  • If the flag is still true after processing all nodes, we return true to indicate that the binary tree satisfies the required conditions. Otherwise, we return false.
     
  • In this example, the binary tree satisfies the required conditions since all nodes in even levels are increasing and in odd levels are decreasing. Therefore, the function would return true.
satisfies

C++ implementation

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class CNode {
public:
   int val;
   CNode* left;
   CNode* right;

   CNode(int v) {
       val = v;
       left = nullptr;
       right = nullptr;
   }
};

bool checkEvenOddLevels(CNode* root) {
   // Return true if the root node is null
   if (root == nullptr) {
       return true;
   }

   // Create a queue to store the nodes of the tree in level order
   queue<CNode*> q;
   q.push(root);

   // Initialize the level to 0, the last value seen to 0, and the flag to true
   int level = 0;
   int last = 0;
   bool flag = true;

   // While the queue is not empty, process the nodes in each level
   while (!q.empty()) {
       // Get the number of nodes in the current level
       int size = q.size();

       // Process the nodes in the current level
       for (int i = 0; i < size; i++) {
           // Get the first node in the queue
           CNode* temp = q.front();
           q.pop();

           // Add the left and right child nodes to the queue if they exist
           if (temp->left != nullptr) {
               q.push(temp->left);
           }

           if (temp->right != nullptr) {
               q.push(temp->right);
           }

           // Check if the level is even
           if (level % 2 == 0) {
               // Check if the value of the current node is greater than the last value seen
               if (i != 0 && temp->val <= last) {
                   flag = false;
               }
           } 
           else {
               // For Odd levels
               // Check if the value of the current node is less than the last value seen
               if (i != 0 && temp->val >= last) {
                   flag = false;
               }
           }

           // Update the last value seen to the value of the current node
           last = temp->val;
       }

       // Increment the level counter
       level++;
   }

   // Return the flag indicating if the binary tree satisfies the conditions
   return flag;
}

int main() {
   CNode* root = new CNode(2);
   root->left = new CNode(8);
   root->right = new CNode(3);
   root->left->left = new CNode(5);
   root->left->right = new CNode(7);
   root->right->left = new CNode(9);
   root->right->right = new CNode(10);

   if (checkEvenOddLevels(root)) {
       cout << "The binary tree satisfies the conditions." << endl;
   } 
   else {
       cout << "The binary tree does not satisfy the conditions." << endl;
   }
   return 0;
}

Main Function Parameter

       2

   /      \

 8        3

 /   \    /    \ 

5   7  9  10 

Output

Output

Java Implementation

import java.util.*;

// Define the CNode class with integer value, left child, and right child
class CNode {
   int val;
   CNode left;
   CNode right;

   public CNode(int val) {
       this.val = val;
       left = null;
       right = null;
   }
}

class Solution {

   // Define the checkEvenOddLevels function that takes a root node and returns a boolean value
   public static boolean checkEvenOddLevels(CNode root) {
       // Return true if the root node is null
       if (root == null) {
           return true;
       }

       // Create a queue to store the nodes of the tree in level order
       Queue<CNode> queue = new LinkedList<>();
       queue.add(root);

       // Initialize the level to 0, the last value seen to 0, and the flag to true
       int level = 0;
       int last = 0;
       boolean flag = true;

       // While the queue is not empty, process the nodes in each level
       while (!queue.isEmpty()) {
           // Get the number of nodes in the current level
           int size = queue.size();

           // Process the nodes in the current level
           for (int i = 0; i < size; i++) {
               // Get the first node in the queue
               CNode temp = queue.poll();

               // Add the left and right child nodes to the queue if they exist
               if (temp.left != null) {
                   queue.add(temp.left);
               }

               if (temp.right != null) {
                   queue.add(temp.right);
               }

               // Check if the level is even
               if (level % 2 == 0) {
                   // Check if the value of the current node is greater than the last value seen
                   if (i != 0 && temp.val <= last) {
                       flag = false;
                   }
               } 
               else {
                   // Check of odd levels
                   // Check if the value of the current node is less than the last value seen
                   if (i != 0 && temp.val >= last) {
                       flag = false;
                   }
               }

               // Update the last value seen to the value of the current node
               last = temp.val;
           }

           // Increment the level counter
           level++;
       }

       // Return the flag indicating if the binary tree satisfies the conditions
       return flag;
   }

   public static void main(String[] args) {
       // Create a binary tree with the root node having value 1, two children with values 3 and 5, and so on
       CNode root = new CNode(2);
       root.left = new CNode(8);
       root.right = new CNode(3);
       root.left.left = new CNode(5);
       root.left.right = new CNode(7);
       root.right.left = new CNode(9);
       root.right.right = new CNode(10);

       // Call the checkEvenOddLevels function on the binary tree
       boolean result = checkEvenOddLevels(root);

       // Print the result
       if (result) {
           System.out.println("The binary tree satisfies the conditions.");
       } else {
           System.out.println("The binary tree does not satisfy the conditions.");
       }
   }
}

Main Function Parameter

      2

   /      \

 8        3

 /   \    /    \ 

5   7  9  10 

Output

Output

Complexities

Time complexity

O(N), where n is the number of nodes in the tree.

Reason: This is because we are visiting each node once and processing its value and children.

Space Complexity

O(W), where W is the width of the binary tree.

Reason:  This is because we are using a queue to store the nodes to be processed, and at most, we will have all the nodes of a level in the queue. In the worst-case scenario, the binary tree is a complete binary tree, so the width is O(n). In this case, the space complexity is O(n).

Frequently asked questions

What is the purpose of the algorithm?

The purpose of the algorithm is to determine if a given binary tree is an Even-Odd Tree. The algorithm checks if the values of the nodes in the tree follow the strict order pattern defined for Even-Odd Trees.

What is an Even-Odd Tree?

An Even-Odd Tree is a binary tree where all the values in the nodes of even levels (the root is considered level 0) are in strictly increasing order, and all the values in the nodes of odd levels are in strictly decreasing order.

How to find out if an array/vector is sorted in increasing?

One way to check is to traverse the whole array/vector and see if each current element is greater than its previous element.

Another way is to use the in-built is_sorted() function. It returns true if the array/vector is sorted in ascending order. Otherwise false.

What is the difference between a binary tree and a binary search tree?

A binary tree is a general data structure, while a binary search tree is a special type of binary tree that satisfies a specific ordering property: for any given node, all nodes in its left subtree must have values less than the node's value, and all nodes in its right subtree must have values greater than the node's value.

What is the height of a binary tree?

The height of a binary tree is the number of edges on the longest path from the root to a leaf node.

Conclusion

In this article, we’ve discussed a problem related to the binary tree. To solve it, we traversed the whole tree level by level. This kind of traversal is called Breadth-first traversal. 

Recommended Problems:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Check if the leaf traversal of two Binary Trees is same?
Next article
Maximum Level Sum in N-ary Tree
Live masterclass