Given a binary tree, the task is to check whether the nodes in this tree form an arithmetic progression, geometric progression or harmonic progression.
Examples:
Input:
4
/ \
2 16
/ \ / \
1 8 64 32
Output: Geometric Progression
Explanation:
The nodes of the binary tree can be used
to form a Geometric Progression as follows -
{1, 2, 4, 8, 16, 32, 64}
Input:
15
/ \
5 10
/ \ \
25 35 20
Output: Arithmetic Progression
Explanation:
The nodes of the binary tree can be used
to form a Arithmetic Progression as follows -
{5, 10, 15, 20, 25, 35}
Approach: The idea is to traverse the Binary Tree using Level-order Traversal and store all the nodes in an array and then check that the array can be used to form an arithmetic, geometric or harmonic progression.
- To check a sequence is in arithmetic progression or not, sort the sequence and check that the common difference between consecutive elements of the array is the same.
- To check a sequence is in geometric progression or not, sort the sequence and check that the common ratio between the consecutive elements of the array is the same.
- To check a sequence is in harmonic progression or not, find the reciprocal of every element and then sort the array and check that the common difference between the consecutive elements is the same.
Below is the implementation of the above approach:
C++
// C++ implementation to check that// nodes of binary tree form AP/GP/HP#include <bits/stdc++.h>using namespace std;// Structure of the// node of the binary treestruct Node { int data; struct Node *left, *right;};// Function to find the size// of the Binary Treeint size(Node* node){ // Base Case if (node == NULL) return 0; else return (size(node->left) + 1 + size(node->right));}// Function to check if the permutation// of the sequence form Arithmetic Progressionbool checkIsAP(double arr[], int n){ // If the sequence contains // only one element if (n == 1) return true; // Sorting the array sort(arr, arr + n); double d = arr[1] - arr[0]; // Loop to check if the sequence // have same common difference // between its consecutive elements for (int i = 2; i < n; i++) if (arr[i] - arr[i - 1] != d) return false; return true;}// Function to check if the permutation// of the sequence form// Geometric progressionbool checkIsGP(double arr[], int n){ // Condition when the length // of the sequence is 1 if (n == 1) return true; // Sorting the array sort(arr, arr + n); double r = arr[1] / arr[0]; // Loop to check if the // sequence have same common // ratio in consecutive elements for (int i = 2; i < n; i++) { if (arr[i] / arr[i - 1] != r) return false; } return true;}// Function to check if the permutation// of the sequence form// Harmonic Progressionbool checkIsHP(double arr[], int n){ // Condition when length of // sequence in 1 if (n == 1) { return true; } double rec[n]; // Loop to find the reciprocal // of the sequence for (int i = 0; i < n; i++) { rec[i] = ((1 / arr[i])); } // Sorting the array sort(rec, rec + n); double d = (rec[1]) - (rec[0]); // Loop to check if the common // difference of the sequence is same for (int i = 2; i < n; i++) { if (rec[i] - rec[i - 1] != d) { return false; } } return true;}// Function to check if the nodes// of the Binary tree forms AP/GP/HPvoid checktype(Node* root){ int n = size(root); double arr[n]; int i = 0; // Base Case if (root == NULL) return; // Create an empty queue // for level order traversal queue<Node*> q; // Enqueue Root and initialize height q.push(root); // Loop to traverse the tree using // Level order Traversal while (q.empty() == false) { Node* node = q.front(); arr[i] = node->data; i++; q.pop(); // Enqueue left child if (node->left != NULL) q.push(node->left); // Enqueue right child if (node->right != NULL) q.push(node->right); } int flag = 0; // Condition to check if the // sequence form Arithmetic Progression if (checkIsAP(arr, n)) { cout << "Arithmetic Progression" << endl; flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsGP(arr, n)) { cout << "Geometric Progression" << endl; flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsHP(arr, n)) { cout << "Geometric Progression" << endl; flag = 1; } else if (flag == 0) { cout << "No"; }}// Function to create new nodestruct Node* newNode(int data){ struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node);}// Driver Codeint main(){ /* Constructed Binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->right = newNode(8); root->right->right->left = newNode(6); root->right->right->right = newNode(7); checktype(root); return 0;} |
Java
// Java implementation to check that // nodes of binary tree form AP/GP/HP import java.util.*;class GFG { // Structure of the // node of the binary tree static class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } }; // Function to find the size // of the Binary Tree static int size(Node node) { // Base Case if (node == null) return 0; else return (size(node.left) + 1 + size(node.right)); } // Function to check if the permutation // of the sequence form Arithmetic Progression static boolean checkIsAP(double[] arr, int n) { // If the sequence contains // only one element if (n == 1) return true; // Sorting the array Arrays.sort(arr); double d = arr[1] - arr[0]; // Loop to check if the sequence // have same common difference // between its consecutive elements for (int i = 2; i < n; i++) if (arr[i] - arr[i - 1] != d) return false; return true; } // Function to check if the permutation // of the sequence form // Geometric progression static boolean checkIsGP(double[] arr, int n) { // Condition when the length // of the sequence is 1 if (n == 1) return true; // Sorting the array Arrays.sort(arr); double r = arr[1] / arr[0]; // Loop to check if the // sequence have same common // ratio in consecutive elements for (int i = 2; i < n; i++) { if (arr[i] / arr[i - 1] != r) return false; } return true; } // Function to check if the permutation // of the sequence form // Harmonic Progression static boolean checkIsHP(double[] arr, int n) { // Condition when length of // sequence in 1 if (n == 1) { return true; } double[] rec = new double[n]; // Loop to find the reciprocal // of the sequence for (int i = 0; i < n; i++) { rec[i] = ((1 / arr[i])); } // Sorting the array Arrays.sort(rec); double d = (rec[1]) - (rec[0]); // Loop to check if the common // difference of the sequence is same for (int i = 2; i < n; i++) { if (rec[i] - rec[i - 1] != d) { return false; } } return true; } // Function to check if the nodes // of the Binary tree forms AP/GP/HP static void checktype(Node root) { int n = size(root); double[] arr = new double[n]; int i = 0; // Base Case if (root == null) return; // Create an empty queue // for level order traversal Queue<Node> q = new LinkedList<>(); // Enqueue Root and initialize height q.add(root); // Loop to traverse the tree using // Level order Traversal while (q.isEmpty() == false) { Node node = q.poll(); arr[i] = node.data; i++; // Enqueue left child if (node.left != null) q.add(node.left); // Enqueue right child if (node.right != null) q.add(node.right); } int flag = 0; // Condition to check if the // sequence form Arithmetic Progression if (checkIsAP(arr, n)) { System.out.println("Arithmetic Progression"); flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsGP(arr, n)) { System.out.println("Geometric Progression"); flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsHP(arr, n)) { System.out.println("Geometric Progression"); flag = 1; } else if (flag == 0) { System.out.println("No"); } } // Driver Code public static void main(String[] args) { /* Constructed Binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.right = new Node(8); root.right.right.left = new Node(6); root.right.right.right = new Node(7); checktype(root); }}// This code is contributed by// sanjeev2552 |
Python3
# Python implementation to check that# nodes of binary tree form AP/GP/HP# class of the# node of the binary treeclass Node: def __init__(self, key): self.left = None self.right = None self.data = key# Function to find the size# of the Binary Treedef size(node): # Base Case if node == None: return 0 else: return (size(node.left) + 1 + size(node.right))# Function to check if the permutation# of the sequence form Arithmetic Progressiondef checkIsAP(arr, n): # If the sequence contains # only one element if n == 1: return 1 # Sorting the array arr.sort() d = arr[1] - arr[0] # Loop to check if the sequence # have same common difference # between its consecutive elements for i in range(2, n): if (arr[i] - arr[i - 1] != d): return 0 return 1# Function to check if the permutation# of the sequence form# Geometric progressiondef checkIsGP(arr, n): # Condition when the length # of the sequence is 1 if (n == 1): return 1 # Sorting the array arr.sort() r = arr[1] / arr[0] # Loop to check if the # sequence have same common # ratio in consecutive elements for i in range(2, n): if (arr[i] / arr[i - 1] != r): return 0 return 1# Function to check if the permutation# of the sequence form# Harmonic Progressiondef checkIsHP(arr, n): # Condition when length of # sequence in 1 if (n == 1): return 1 rec = [None] * n # Loop to find the reciprocal # of the sequence for i in range(0, n): rec[i] = ((1 / arr[i])) # Sorting the array rec.sort() d = (rec[1]) - (rec[0]) # Loop to check if the common # difference of the sequence is same for i in range(2, n): if (rec[i] - rec[i - 1] != d): return 0 return 1# Function to check if the nodes# of the Binary tree forms AP/GP/HPdef checktype(root): n = size(root) arr = [Node] * n i = 0 # Base Case if (root == None): return # Create an empty queue # for level order traversal q = [] # Enqueue Root and initialize height q.append(root) # Loop to traverse the tree using # Level order Traversal while (len(q) > 0): node = q[0] arr[i] = node.data i = i + 1 q.pop(0) # Enqueue left child if (node.left != None): q.append(node.left) # Enqueue right child if (node.right != None): q.append(node.right) flag = 0 # Condition to check if the # sequence form Arithmetic Progression if (checkIsAP(arr, n)): print("Arithmetic Progression\n") flag = 1 # Condition to check if the # sequence form Geometric Progression elif (checkIsGP(arr, n)): print("Geometric Progression\n") flag = 1 # Condition to check if the # sequence form Geometric Progression elif (checkIsHP(arr, n)): print("Harmonicc Progression\n") flag = 1 elif (flag == 0): print("No")# Driver Code # Constructed Binary tree is: # 1 # / \ # 2 3 # / \ \ # 4 5 8 # / \ # 6 7root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.right = Node(8)root.right.right.left = Node(6)root.right.right.right = Node(7)checktype(root)# This code is contributed by rj13to. |
C#
// C# implementation to check that // nodes of binary tree form AP/GP/HP using System;using System.Collections.Generic;public class GFG { // Structure of the // node of the binary tree public class Node { public int data; public Node left, right; public Node(int data) { this.data = data; this.left = this.right = null; } }; // Function to find the size // of the Binary Tree static int size(Node node) { // Base Case if (node == null) return 0; else return (size(node.left) + 1 + size(node.right)); } // Function to check if the permutation // of the sequence form Arithmetic Progression static bool checkIsAP(double[] arr, int n) { // If the sequence contains // only one element if (n == 1) return true; // Sorting the array Array.Sort(arr); double d = arr[1] - arr[0]; // Loop to check if the sequence // have same common difference // between its consecutive elements for (int i = 2; i < n; i++) if (arr[i] - arr[i - 1] != d) return false; return true; } // Function to check if the permutation // of the sequence form // Geometric progression static bool checkIsGP(double[] arr, int n) { // Condition when the length // of the sequence is 1 if (n == 1) return true; // Sorting the array Array.Sort(arr); double r = arr[1] / arr[0]; // Loop to check if the // sequence have same common // ratio in consecutive elements for (int i = 2; i < n; i++) { if (arr[i] / arr[i - 1] != r) return false; } return true; } // Function to check if the permutation // of the sequence form // Harmonic Progression static bool checkIsHP(double[] arr, int n) { // Condition when length of // sequence in 1 if (n == 1) { return true; } double[] rec = new double[n]; // Loop to find the reciprocal // of the sequence for (int i = 0; i < n; i++) { rec[i] = ((1 / arr[i])); } // Sorting the array Array.Sort(rec); double d = (rec[1]) - (rec[0]); // Loop to check if the common // difference of the sequence is same for (int i = 2; i < n; i++) { if (rec[i] - rec[i - 1] != d) { return false; } } return true; } // Function to check if the nodes // of the Binary tree forms AP/GP/HP static void checktype(Node root) { int n = size(root); double[] arr = new double[n]; int i = 0; // Base Case if (root == null) return; // Create an empty queue // for level order traversal Queue<Node> q = new Queue<Node>(); // Enqueue Root and initialize height q.Enqueue(root); // Loop to traverse the tree using // Level order Traversal while (q.Count!=0 == false) { Node node = q.Dequeue(); arr[i] = node.data; i++; // Enqueue left child if (node.left != null) q.Enqueue(node.left); // Enqueue right child if (node.right != null) q.Enqueue(node.right); } int flag = 0; // Condition to check if the // sequence form Arithmetic Progression if (checkIsAP(arr, n)) { Console.WriteLine("Arithmetic Progression"); flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsGP(arr, n)) { Console.WriteLine("Geometric Progression"); flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsHP(arr, n)) { Console.WriteLine("Geometric Progression"); flag = 1; } else if (flag == 0) { Console.WriteLine("No"); } } // Driver Code public static void Main(String[] args) { /* Constructed Binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.right = new Node(8); root.right.right.left = new Node(6); root.right.right.right = new Node(7); checktype(root); }}// This code contributed by sapnasingh4991 |
Javascript
<script> // JavaScript implementation to check that // nodes of binary tree form AP/GP/HP // Structure of the // node of the binary tree class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to find the size // of the Binary Tree function size(node) { // Base Case if (node == null) return 0; else return (size(node.left) + 1 + size(node.right)); } // Function to check if the permutation // of the sequence form Arithmetic Progression function checkIsAP(arr, n) { // If the sequence contains // only one element if (n == 1) return true; // Sorting the array arr.sort(); let d = arr[1] - arr[0]; // Loop to check if the sequence // have same common difference // between its consecutive elements for (let i = 2; i < n; i++) if (arr[i] - arr[i - 1] != d) return false; return true; } // Function to check if the permutation // of the sequence form // Geometric progression function checkIsGP(arr, n) { // Condition when the length // of the sequence is 1 if (n == 1) return true; // Sorting the array arr.sort(); let r = arr[1] / arr[0]; // Loop to check if the // sequence have same common // ratio in consecutive elements for (let i = 2; i < n; i++) { if (arr[i] / arr[i - 1] != r) return false; } return true; } // Function to check if the permutation // of the sequence form // Harmonic Progression function checkIsHP(arr, n) { // Condition when length of // sequence in 1 if (n == 1) { return true; } let rec = new Array(n); // Loop to find the reciprocal // of the sequence for (let i = 0; i < n; i++) { rec[i] = ((1 / arr[i])); } // Sorting the array rec.sort(); let d = (rec[1]) - (rec[0]); // Loop to check if the common // difference of the sequence is same for (let i = 2; i < n; i++) { if (rec[i] - rec[i - 1] != d) { return false; } } return true; } // Function to check if the nodes // of the Binary tree forms AP/GP/HP function checktype(root) { let n = size(root); let arr = new Array(n); let i = 0; // Base Case if (root == null) return; // Create an empty queue // for level order traversal let q = []; // Enqueue Root and initialize height q.push(root); // Loop to traverse the tree using // Level order Traversal while (q.length > 0) { let node = q[0]; q.shift(); arr[i] = node.data; i++; // Enqueue left child if (node.left != null) q.push(node.left); // Enqueue right child if (node.right != null) q.push(node.right); } let flag = 0; // Condition to check if the // sequence form Arithmetic Progression if (checkIsAP(arr, n)) { document.write("Arithmetic Progression"); flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsGP(arr, n)) { document.write("Geometric Progression"); flag = 1; } // Condition to check if the // sequence form Geometric Progression else if (checkIsHP(arr, n)) { document.write("Geometric Progression"); flag = 1; } else if (flag == 0) { document.write("No"); } } /* Constructed Binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.right = new Node(8); root.right.right.left = new Node(6); root.right.right.right = new Node(7); checktype(root);</script> |
Output:
Arithmetic Progression
Performance Analysis:
- Time Complexity: As in the above approach, there is a traversal of the nodes and sorting them which takes O(N*logN) time in worst case. Hence the Time Complexity will be O(N*logN).
- Auxiliary Space Complexity: As in the above approach, There is extra space used to store the data of the nodes. Hence the auxiliary space complexity will be 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!
