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

Locked Binary Tree

Easy
0/40
Average time to solve is 8m
Contributed by

Problem statement

Given array ‘PAR’ of size ‘N’, representing a binary tree, where ‘PAR[i]’ denotes the parent of node ‘i’. And a binary array ‘LOCK’ of ‘N’ integers, ‘LOCK[i] = 1’ means the ‘ith’ node is locked. Find out whether a target node ‘K’ can be locked or not.

A node will be locked only when some or all of the ancestors or the node itself is locked.

EXAMPLE:
``````Input:
'N' = 5, ‘K’ = 3
‘ARR’ = [-1, 0, 0, 1, 2]
‘LOCK’ = [0, 0, 1, 0, 0]

Output: ‘1’
``````

``````In the above tree in the simple path from node ‘4’ to root ‘1,’ the nodes encountered are [0, 1, 3], and no node from the set is locked. Hence node ‘3’ can be locked.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= 'T' <= 10
1 <= 'N' <= 10^5
0 <= ‘K’ <= ‘N-1’
0 <= ‘PAR[i]’ <= ‘N-1’
0 <= ‘LOCK[i]’ <= 1

Time Limit: 1 sec
``````
Sample Input 1 :
``````2
5 0
-1 0 3 0 3
1 1 1 0 0
4 1
3 2 -1 1
1 0 0 1
``````
Sample Output 1 :
``````0
1
``````
Explanation Of Sample Input 1 :
``````In the first test case,
``````

``````In the above tree the target node ‘0’ is itself locked, so it cannot be locked.
Hence the answer is ‘false’.

In the second test case,
``````

``````In the above tree in the simple path from node ‘1’ to root ‘2’ the nodes encountered are [1, 2], and no node from the set is locked.
Hence the answer is ‘true’.
``````
Sample Input 2 :
``````2
4 2
-1 0 1 1
0 1 0 0
4 3
-1 0 1 2
1 0 0 0
``````
Sample Output 2 :
``````0
0
``````
Console