PROBLEM LINK
Author: Shivam Anand
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Knowledge of Trees, Binary Trees, Tree Traversal, Recursion
PROBLEM:
You are given the height of a Binary Tree. And the maximum number of elements a Binary Tree of height h can hold. Arrange the elements properly and form a Binary Tree. Next, Find the Circumference and Diameter of the Tree. The definition of Circumference is ‘The total no of leaf nodes’ and Diameter is ‘Maximum distance between any two Leaf Nodes in Binary Tree, calculate the value of Pi for the tree. The definition of pi is inferred from basic geometry i.e. Pi=\frac{c}{d}
EXPLANATION:
The problem can be divided into 3 main parts
1 Create a Binary Tree
2 Find Circumference
3 Find Diameter
1 Create a Binary Tree
Every Breadth/Layer in Binary Tree contains 2^n elements
To retrieve any left node from the input: 2 * (–height of the particular node) +1
To retrieve any left node from the input: 2 * (–height of the particular node +2)
Retrieve each item from the input and arrange each them in the node recursively.
2 Find Circumference:
Whenever a no left or right node is detected, it becomes a leaf node and the counter is increased by 1. Traverse the tree recursively, visit each item and check every item for sub-item.
3 Find Diameter:
To find the diameter of Tree the logic used is maximum_value_of(height of left subtree+height of right subtree, diameter of left subtree, diameter of right subtree)
The diameter has to be within these 3 values.
This applies at each level of the Tree.
To find the height of any segment of a tree is very much similar to finding the circumference. Find leaf nodes with null values recursively traversing every node and get the maximum height out of them at each level of the tree.
Time Complexity
Tree Traversal O(n)
Diameter O(n^2)
Overall O(n^2)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
struct Node // Tree
{
int data;
Node *left, *right;
};
Node *newNode(int data) // add a new node to existing node
{
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
int height(struct Node *node) //recursive approach
{
if (node == NULL)
return 0;
return 1 + max(height(node->left), height(node->right));
}
int diameter(struct Node *tree) //recursive approach
{
if (tree == NULL)
return 0;
int lheight = height(tree->left);
int rheight = height(tree->right);
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
return max(lheight + rheight + 1, max(ldiameter, diameter));
}
unsigned int getLeafCount(struct Node *node)//recursive approach
{
if (node == NULL)
return 0;
if (node->left == NULL && node->right == NULL)
return 1;
else
return getLeafCount(node->left) +getLeafCount(node->right);
}
Node *insertLevelOrder(int arr[], Node *root,int i, int n)//recursive approach
{
if (i < n)
{
if (arr[i] != -1)//ignore dummy values
{
Node *temp = newNode(arr[i]);
root = temp;
root->left = insertLevelOrder(arr,root->left, 2 * i + 1, n);
root->right = insertLevelOrder(arr,root->right, 2 * i + 2, n);
}
}
return root;
}
void solve()
{
int h;
cin>>h;
int no=pow(2,h)-1;
int arr[no];
for (int i = 0; i < no; i++)
{
cin>>arr[i];
}
int n = sizeof(arr) / sizeof(arr[0]);
Node *root = insertLevelOrder(arr, root, 0, n); //arrange the integers systematically
and create a Binary Tree
int c = getLeafCount(root);//get circumference which is also equal to the no of leaf
count
int d = diameter(root);//get diameter
double answer = (double)c / d;// apply pi=c/d
printf("%.4f", answer);// print answer correct to 4 decimal places
}
int main()
{
clock_t time_req;
time_req = clock();
cin.sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}