FastPrepLockable Nodes in a Binary Search Tree
Problems/Lockable Nodes in a Binary Search Tree

Lockable Nodes in a Binary Search Tree

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a technical and HR round of a Nutanix on-campus internship drive, in a report posted in 2017. The candidate got a binary search tree whose nodes carry a locked flag. They had to say whether a given node can be locked. That is only allowed when no ancestor and no node in its subtree is locked. After a brute force answer, the interviewer asked for something faster. The candidate precomputed whether each subtree holds a locked node.

The report gives no input format, sizes, or result for many checks. Here the tree comes as a TreeNode root, and the locked nodes come as a list of values. You answer up to 10^5 queries. You return how many of them name a node that can be locked, counting repeats each time. A node that is already locked counts as not lockable. The tree has up to 5 * 10^4 nodes, distinct values from 1 to 10^5, and at most 20 levels. The largest tests are too slow if you check a whole subtree on every query.

Our version is about 85% the same as the reported question.

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[]) → int

Examples

Example 1

root = [4,2,6,1,3,5,7]locked = [6]queries = [2,4,5,1]return = 2
root
4213657

Node 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 = 3
root
534879

No 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 = 1
root
105271520

Node 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 n nodes, where 1 <= 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 in locked are distinct, and each is the value of a node in the tree.
  • 1 <= queries.length <= 10^5, and each queries[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

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countLockable(TreeNode root, int[] locked, int[] queries) {
        // Write your code here.
    }
}
Checking account…