Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
674 views
in Online Assessments by Expert (111,330 points) | 674 views

1 Answer

0 like 0 dislike

Given a "balanced" (not sure) binary tree. Find the lucky quadruplets, which is definied as an unordered set of 4 nodes such that all the nodes in the set are distinct and we can choose a node from that set to be the centre such that the distance of the other 3 nodes from the selected node is the same.
Input Format:

 

  • The first line contains an integer N denoting the number of nodes in the tree
  • Then next line contains N space separated integers denoting the parent array where : parent[i] is the parent of the node i
  • You may assume that the given parent array corresponds to a balanced binary tree.

 

Constraints

 

  • 1 <= N <= 10^5

 

Sample Input
7
0112233
Sample Output
6

by Expert (111,330 points)