Lockable Nodes in a Binary Search Tree
Updated
Problem statement
You are given the root of a binary search tree whose node values are all different. Some nodes are locked: locked holds their values.
A node can be locked only when none of these nodes is locked:
- the node itself,
- any node in its subtree (its children, their children, and so on),
- any of its ancestors (its parent, its parent's parent, and so on up to the root).
Each queries[i] is the value of a node in the tree. Return how many entries of queries name a node that can be locked. A node that appears several times in queries is counted each time. Queries only ask; they never lock anything, so their order does not matter.
Function
countLockable(root: TreeNode, locked: int[], queries: int[]) → intExamples
Example 1
root = [4,2,6,1,3,5,7]locked = [6]queries = [2,4,5,1]return = 2Node 2 and node 1 can be locked: no node above them and no node below them is locked. Node 4 cannot, because the locked node 6 is in its subtree. Node 5 cannot, because its parent 6 is locked. So the answer is 2.
Example 2
root = [5,3,8,null,4,7,9]locked = []queries = [5,5,9]return = 3No node is locked, so every query is a yes. Node 5 is asked twice and counts twice, so the answer is 3.
Example 3
root = [10,5,15,2,7,null,20]locked = [7,20]queries = [7,2,15,10]return = 1Node 7 is already locked, so it cannot be locked. Node 2 can: its ancestors 5 and 10 are not locked and it has no children. Node 15 cannot, because its child 20 is locked. Node 10 cannot, because locked nodes lie below it. So the answer is 1.
Constraints
- The tree has
nnodes, where1 <= n <= 5 * 10^4. 1 <= Node.val <= 10^5, and all node values are distinct.- The tree is a valid binary search tree with at most 20 levels (the root is on level 1).
0 <= locked.length <= n, the values inlockedare distinct, and each is the value of a node in the tree.1 <= queries.length <= 10^5, and eachqueries[i]is the value of a node in the tree.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Maximum Sum Among Longest Root-to-Leaf PathsAmazon · ONSITE INTERVIEW
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Onion-Peel Layers of a Binary TreeeBay · ONSITE INTERVIEWeBay interview questions
- Match a Descendant Selector in a DOM TreeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions