Dado un árbol binario , la tarea es verificar si los Nodes en este árbol forman una progresión aritmética , una progresión geométrica o una progresión armónica .
Ejemplos:
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}
Enfoque: la idea es atravesar el árbol binario utilizando el recorrido transversal por niveles y almacenar todos los Nodes en una array y luego comprobar que la array se puede utilizar para formar una progresión aritmética, geométrica o armónica .
- Para verificar que una secuencia esté en progresión aritmética o no, ordene la secuencia y verifique que la diferencia común entre los elementos consecutivos de la array sea la misma.
- Para verificar que una secuencia esté en progresión geométrica o no, ordene la secuencia y verifique que la proporción común entre los elementos consecutivos de la array sea la misma.
- Para verificar que una secuencia esté en progresión armónica o no, encuentre el recíproco de cada elemento y luego ordene la array y verifique que la diferencia común entre los elementos consecutivos sea la misma.
A continuación se muestra la implementación del enfoque anterior:
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 tree
struct Node {
int data;
struct Node *left, *right;
};
// Function to find the size
// of the Binary Tree
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
bool 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 progression
bool 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 Progression
bool 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/HP
void 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 node
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Driver Code
int 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 tree
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.data = key
# Function to find the size
# of the Binary Tree
def 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 Progression
def 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 progression
def 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 Progression
def 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/HP
def 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 7
root = 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>
Producción:
Arithmetic Progression
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, hay un recorrido de los Nodes y su clasificación, lo que toma un tiempo O (N * logN) en el peor de los casos. Por lo tanto, la complejidad del tiempo será O(N*logN) .
- Complejidad del espacio auxiliar: como en el enfoque anterior, se utiliza espacio adicional para almacenar los datos de los Nodes. Por lo tanto, la complejidad del espacio auxiliar será O(N) .