Update appNew update is available. Click here to update.

Locked Binary Tree

profile
Contributed by
Rakesh Tiwari
Easy
yellow-spark
0/40
8 mins
100 %
2 upvotes
Walmart

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
Full screen
Reset Code
Full screen
Autocomplete
copy-code
Console