TREEPI - Editorial



Author: Shivam Anand




Knowledge of Trees, Binary Trees, Tree Traversal, Recursion


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}


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)


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;
        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;
    int no=pow(2,h)-1;

    int arr[no];
    for (int i = 0; i < no; 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 
    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();


    return 0;