Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Validate Binary Tree Nodes

Moderate
0/80
Average time to solve is 15m
9 upvotes
Asked in companies
FacebookMakeMyTripIntuit

Problem statement

You are given ‘N’ binary tree nodes numbered from 0 to N - 1 where node ‘i’ has two children LEFT_CHILD[i] and RIGHT_CODE[i]. Return ‘True’ if and only if all the given nodes form exactly one valid binary tree. If node ‘i’ has no left child then 'LEFT_CHILD[i]' will equal -1, similarly for the right child.

Example:

Let’s say we have n=4 nodes, 'LEFT_CHILD' = {1, -1, 3, -1} and 
RIGHT_CHILD = {2, -1, -1, -1}. So the resulting tree will look like this:

It will return True as there is only one valid binary tree and each node has only one parent and there is only one root.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
1 <= N <= 10^4
LEFT_CHILD.length == RIGHT_CHILD.length == N
-1 <= LEFT_CHILD[i], RIGHT_CHILD[i] <= N - 1

Time Limit: 1 sec
Sample Input 1:
2
4
1 -1 3 -1
2 -1 -1 -1
4
1 -1 3 -1
2 3 -1 -1
Sample Output 1:
Yes
No
Explanation 1:
For the first test case, 
It is already explained above in the example.

For the second test case, 
The resulting tree from the given input will be :

So the output will be ‘False’ because node 3 has two parents 1 
and 2.
Sample Input 2:
2
2
1 0
-1 -1
6
1 -1 -1 4 -1 -1
2 -1 -1 5 -1 -1
Sample Output 2:
 No
 No
Full screen
Console