BinaryTreeAndPermutation | Topcoder Archive

Problem Statement

A full binary tree is a rooted tree with the following property: each vertex that is not a leaf has exactly two children - a left child and a right child.

You have a full binary tree. The tree has n vertices, numbered 0 through n-1. You are given the int[]s lef and rig that describe the shape of the tree. If vertex i is a leaf we have lef[i] = rig[i] = -1. Otherwise, lef[i] is the left child and rig[i] is the right child of vertex i.

The ancestors of vertex x are the vertices on the unique path from x to the root of the tree, including x and the root. The least common ancestor of x and y, denoted LCA(x,y), is the first vertex on the path from x to the root that is also the ancestor of y. Equivalently, among all vertices that are ancestors of both x and y, LCA(x,y) is the one that is farthest away from the root.

We are looking for a permutation p of {0, 1, ..., n-1}. You are given a set of m constraints this permutation has to satisfy. More precisely, you are given the int[]s a, b, and c, each with m elements. For each valid i we get one constraint: LCA( p[a[i]], p[b[i]] ) must be c[i].

If there is at least one permutation with the above properties, find and return one such permutation. Otherwise, return an empty int[].

Definition

Class:: BinaryTreeAndPermutation
Method:: findPermutation
Parameters:: int[], int[], int[], int[], int[]
Returns:: int[]
Method signature:: int[] findPermutation(int[] lef, int[] rig, int[] a, int[] b, int[] c)
(be sure your method is public)

Constraints

n, m will be between 1 and 50, inclusive.
lef and rig will contain exactly n elements.
For each i, lef[i]=rig[i]=-1 or (i<lef[i],rig[i]<n and lef[i] != rig[i]).
lef and rig will describe a binary tree.
a, b, c will contain exactly m elements.
Each element in a, b, c will be between 0 and n-1, inclusive.

Examples

```
{1,-1,-1}
```
```
{2,-1,-1}
```
```
{2,1}
```
```
{2,0}
```
```
{0,0}
```
```
Returns: {2, 1, 0 }
```
The tree looks as follows: 0 / \ 1 2 We are given two constraints: LCA( p[2], p[2] ) should be 0, and LCA( p[1], p[0] ) should also be 0. The first constraint implies that p[2] must be 0. This leaves us with two possible permutations: {2,1,0} and {1,2,0}. We can easily verify that they both satisfy the second constraint as well, so each of them is a valid answer.
```
{1,-1,-1}
```
```
{2,-1,-1}
```
```
{2,1}
```
```
{2,0}
```
```
{0,1}
```
```
Returns: { }
```
We have the same tree and the same first constraint. The second constraint now requires that LCA( p[1], p[0] ) should be 1. As we saw in Example 0, there is no permutation p with this property.

{1,-1,3,-1,-1}

{2,-1,4,-1,-1}

{3,0,0,0}

{3,1,2,4}

{0,0,0,0}

Returns: {1, 3, 4, 0, 2 }

{1,-1,3,-1,-1}

{2,-1,4,-1,-1}

{3,0,0,1}

{3,1,2,4}

{0,0,0,0}

Returns: { }

{1,-1,3,-1,-1}

{2,-1,4,-1,-1}

{1,2}

{2,1}

{0,1}

Returns: { }

{1,3,5,-1,-1,7,-1,-1,-1}

{2,4,6,-1,-1,8,-1,-1,-1}

{6,6,7,7,3,8,5,3}

{4,3,7,1,0,0,0,5}

{1,0,1,0,2,2,2,5}

Returns: {2, 0, 7, 5, 4, 8, 3, 1, 6 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.