Tree - Find the smallest non-negative integer | AskTheCode

Find the smallest non-negative integer in sub-tree | Tree in CPP | Ask The Code

---

Problem:

You are given a tree having A nodes numbered from 0 to A-1, rooted at node 0. Each node has a distinct value ranging between [0, A-1], the ith node having value C[i]. (No two nodes have some value). For each node in the tree, you have to find the smallest non-negative integer value which is not present in the subtree of that node.

Constraint:

• 1 <= A <= 10^5

• 0 <= B[i][0], B[i][1] <= A-1

• B[i][0] != B[i][1]

• 0 <= C[i] <= A-1

• All C[i] is different.

---

Input Format:

• The first argument is an integer A denoting the number of nodes.

• The second argument is a 2D array B of size (A-1) x 2 where ith edge is between B[i][0] and B[i][1] node.

• The third argument is an integer array C.

Output Format:

Return an integer array, where ith integer denotes the answer for node i.

---

Sample Input 1:

3
0 1
0 2
1 2 0

Sample Output 1:

Resultant Array: [ 3, 0, 1 ]

---

Sample Input 2:

6
0 1 1 2 0 3 3 4 3 5
4 3 5 1 0 2

Sample Output 2:

Resultant Array: [ 6, 0, 0, 3, 1, 0 ]

---

Sample Input 3:

3
0 1
0 2
0 1 2

Sample Output 4:

Resultant Array: [ 3, 0, 0 ]

---

Code:

#include <iostream>
using namespace std;
#define endl "\n"
#define int long long int


int32_t main(){
	int A, min, max = 0;
	cin >> A;
	int B[A][2];
	int C[A], res[A];
	B[0][0] = -1;
	for (int i = 1; i < A; i++)
		cin >> B[i][0] >> B[i][1];
	for (int i = 0; i < A; i++){
		cin >> B[i][1];
	}

	cout << endl;
	// for (int i = 0; i < A; i++)
	// 	cout << B[i][1] << "\t";
	// cout << endl;

	for (int i = 0; i < A; i++){
		max = min = B[i][1];
		if (i == 0){
			for (int j = 1; j < A; j++){
				if (B[j][1] > max)
					max = B[j][1];
				if (B[j][1] < min)
					min = B[j][1];
			}
		}
		else{
			for (int j = 1; j < A; j++){
				if (B[j][0] == i){
					if (B[j][1] > max)
						max = B[j][1];
					if (B[j][1] < min)
						min = B[j][1];
				}
			}
		}
		// cout << "Max: " << max << "  Min: " << min << endl;
		if (min > 0)
			res[i] = 0;
		else
			res[i] = (max+1);
	}
	cout << "Resultant Array: [ ";
	// for (int i = 0; i < A; i++)
	// 	cout << res[i] << "\t";

	for (int i = 0; i < A; i++){
		if (i == A - 1)
			cout << res[i] << " ]" << endl;
		else
			cout << res[i] << ", ";
	}
}

NOTE: You can modify this code further to get the output in your desired format. Also, this code can be further optimized using the Disjoint set.