Question

Facebook | Meta | OA | Software Engineer | 2022 | Set-1

Answer 1

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