Given a Binary Tree, the task is to check if it consists of node values arranged in strictly increasing order at even levels and strictly decreasing at odd levels (Assuming the root node to be at level 0).
Examples:
Input:
2 / \ 6 3 / \ \ 4 7 11 / \ \ 10 5 1Output: YES
Explanation:
At level 1 (odd), Node values 6 and 3 are in strictly decreasing order.
At level 2 (even), Node values 4, 7, and 11 are in strictly increasing order.
At level 3 (odd), Node values 10, 5, and 1) are in strictly decreasing order.
Therefore, the tree satisfies the given conditions.Input:
5 / \ 6 3 / \ \ 4 9 2Output: NO
Approach: The idea is to perform Level Order Traversal on the given Binary Tree and for each level, check if it satisfies the given conditions or not. Follow the steps below to solve the problem:
- Create an empty Queue to store nodes of each level one by one during the Level Order Traversal of the tree.
- Push the root node into the Queue.
- Iterate until the queue is empty and perform the following:
- Keep popping nodes of the current level from the queue and insert it into an Arraylist. Push all of its children nodes into the Queue.
- If the level is even, check if elements present in the Arraylist is in increasing order or not. If found to be true, proceed to the next level. Otherwise, print No.
- Similarly, check for the odd levels.
- After complete traversal of the tree, if all levels are found to be satisfying the conditions, print YES.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;struct Node { int val; Node *left, *right;};struct Node* newNode(int data){ struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->val = data; temp->left = NULL; temp->right = NULL; return temp;}// Function to check if given binary// tree satisfies the required conditionsbool checkEvenOddLevel(Node *root){ if (root == NULL) return true; // Queue to store nodes // of each level queue<Node*> q; q.push(root); // Stores the current // level of the binary tree int level = 0; // Traverse until the // queue is empty while (q.empty()) { vector<int> vec; // Stores the number of nodes // present in the current level int size = q.size(); for(int i = 0; i < size; i++) { Node *node = q.front(); vec.push_back(node->val); // Insert left and right child // of node into the queue if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } // If the level is even if (level % 2 == 0) { // If the nodes in this // level are in strictly // increasing order or not for(int i = 0; i < vec.size() - 1; i++) { if (vec[i + 1] > vec[i]) continue; return false; } } // If the level is odd else if (level % 2 == 1) { // If the nodes in this // level are in strictly // decreasing order or not for(int i = 0; i < vec.size() - 1; i++) { if (vec[i + 1] < vec[i]) continue; return false; } } // Increment the level count level++; } return true;}// Driver Codeint main(){ // Construct a Binary Tree Node *root = NULL; root = newNode(2); root->left = newNode(6); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(7); root->right->right = newNode(11); root->left->left->left = newNode(10); root->left->left->right = newNode(5); root->left->right->right = newNode(1); // Function Call if (checkEvenOddLevel(root)) cout << "YES"; else cout << "NO";}// This code is contributed by ipg2016107 |
Java
// Java Program for the above approachimport java.util.*;class GFG { // Structure of Tree node static class Node { int val; Node left, right; } // Function to create new Tree node static Node newNode(int data) { Node temp = new Node(); temp.val = data; temp.left = null; temp.right = null; return temp; } // Function to check if given binary // tree satisfies the required conditions public static boolean checkEvenOddLevel(Node root) { if (root == null) return true; // Queue to store nodes // of each level Queue<Node> q = new LinkedList<>(); q.add(root); // Stores the current // level of the binary tree int level = 0; // Traverse until the // queue is empty while (!q.isEmpty()) { ArrayList<Integer> list = new ArrayList<>(); // Stores the number of nodes // present in the current level int size = q.size(); for (int i = 0; i < size; i++) { Node node = q.poll(); list.add(node.val); // Insert left and right child // of node into the queue if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); } // If the level is even if (level % 2 == 0) { // If the nodes in this // level are in strictly // increasing order or not for (int i = 0; i < list.size() - 1; i++) { if (list.get(i + 1) > list.get(i)) continue; return false; } } // If the level is odd else if (level % 2 == 1) { // If the nodes in this // level are in strictly // decreasing order or not for (int i = 0; i < list.size() - 1; i++) { if (list.get(i + 1) < list.get(i)) continue; return false; } } // Increment the level count level++; } return true; } // Driver Code public static void main(String[] args) { // Construct a Binary Tree Node root = null; root = newNode(2); root.left = newNode(6); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(7); root.right.right = newNode(11); root.left.left.left = newNode(10); root.left.left.right = newNode(5); root.left.right.right = newNode(1); // Function Call if (checkEvenOddLevel(root)) { System.out.println("YES"); } else { System.out.println("NO"); } }} |
Python3
# Python3 program for the above approach# Tree nodeclass Node: def __init__(self, data): self.left = None self.right = None self.val = data # Function to return new tree node def newNode(data): temp = Node(data) return temp# Function to check if the# tree is even-odd treedef checkEvenOddLevel(root): if (root == None): return True q = [] # Stores nodes of each level q.append(root) # Store the current level # of the binary tree level = 0 # Traverse until the # queue is empty while (len(q) != 0): l = [] # Stores the number of nodes # present in the current level size = len(q) for i in range(size): node = q[0] q.pop(0) # Insert left and right child # of node into the queue if (node.left != None): q.append(node.left); if (node.right != None): q.append(node.right); # If the level is even if (level % 2 == 0): # If the nodes in this # level are in strictly # increasing order or not for i in range(len(l) - 1): if (l[i + 1] > l[i]): continue return False # If the level is odd elif (level % 2 == 1): # If the nodes in this # level are in strictly # decreasing order or not for i in range(len(l) - 1): if (l[i + 1] < l[i]): continue return False # Increment the level count level += 1 return True # Driver codeif __name__=="__main__": # Construct a Binary Tree root = None root = newNode(2) root.left = newNode(6) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(7) root.right.right = newNode(11) root.left.left.left = newNode(10) root.left.left.right = newNode(5) root.left.right.right = newNode(1) # Check if the binary tree # is even-odd tree or not if (checkEvenOddLevel(root)): print("YES") else: print("NO") # This code is contributed by rutvik_56 |
C#
// C# Program for the // above approachusing System;using System.Collections.Generic;class GFG{// Structure of Tree nodepublic class Node { public int val; public Node left, right;}// Function to create // new Tree nodestatic Node newNode(int data){ Node temp = new Node(); temp.val = data; temp.left = null; temp.right = null; return temp;}// Function to check if given binary// tree satisfies the required conditionspublic static bool checkEvenOddLevel(Node root){ if (root == null) return true; // Queue to store nodes // of each level Queue<Node> q = new Queue<Node>(); q.Enqueue(root); // Stores the current // level of the binary tree int level = 0; // Traverse until the // queue is empty while (q.Count != 0) { List<int> list = new List<int>(); // Stores the number of nodes // present in the current level int size = q.Count; for (int i = 0; i < size; i++) { Node node = q.Dequeue(); list.Add(node.val); // Insert left and right child // of node into the queue if (node.left != null) q.Enqueue(node.left); if (node.right != null) q.Enqueue(node.right); } // If the level is even if (level % 2 == 0) { // If the nodes in this // level are in strictly // increasing order or not for (int i = 0; i < list.Count - 1; i++) { if (list[i + 1] > list[i]) continue; return false; } } // If the level is odd else if (level % 2 == 1) { // If the nodes in this // level are in strictly // decreasing order or not for (int i = 0; i < list.Count - 1; i++) { if (list[i + 1] < list[i]) continue; return false; } } // Increment the level count level++; } return true;}// Driver Codepublic static void Main(String[] args){ // Construct a Binary Tree Node root = null; root = newNode(2); root.left = newNode(6); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(7); root.right.right = newNode(11); root.left.left.left = newNode(10); root.left.left.right = newNode(5); root.left.right.right = newNode(1); // Function Call if (checkEvenOddLevel(root)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); }}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Structure of Tree nodeclass Node{ constructor(data) { this.left = null; this.right = null; this.val = data; }}// Function to create new Tree nodefunction newNode(data){ let temp = new Node(data); return temp;}// Function to check if given binary// tree satisfies the required conditionsfunction checkEvenOddLevel(root){ if (root == null) return true; // Queue to store nodes // of each level let q = []; q.push(root); // Stores the current // level of the binary tree let level = 0; // Traverse until the // queue is empty while (q.length > 0) { let list = []; // Stores the number of nodes // present in the current level let size = q.length; for(let i = 0; i < size; i++) { let node = q[0]; q.shift(); list.push(node.val); // Insert left and right child // of node into the queue if (node.left != null) q.push(node.left); if (node.right != null) q.push(node.right); } // If the level is even if (level % 2 == 0) { // If the nodes in this // level are in strictly // increasing order or not for(let i = 0; i < list.length - 1; i++) { if (list[i + 1] > list[i]) continue; return false; } } // If the level is odd else if (level % 2 == 1) { // If the nodes in this // level are in strictly // decreasing order or not for(let i = 0; i < list.length - 1; i++) { if (list[i + 1] < list[i]) continue; return false; } } // Increment the level count level++; } return true;}// Driver code// Construct a Binary Treelet root = null;root = newNode(2);root.left = newNode(6);root.right = newNode(3);root.left.left = newNode(4);root.left.right = newNode(7);root.right.right = newNode(11);root.left.left.left = newNode(10);root.left.left.right = newNode(5);root.left.right.right = newNode(1);// Function Callif (checkEvenOddLevel(root)) { document.write("YES");}else{ document.write("NO");}// This code is contributed by suresh07</script> |
Output:
YES
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
