Binary Search Tree Operations
Updated
Problem statement
Process a sequence of operations on an initially empty set of integer keys. This exercise practices implementing a binary search tree from scratch.
[0, key]: insertkey. If it already exists, leave the set unchanged.[1, key]: search forkey. Append1if it exists, otherwise append0.[2, key]: deletekey. If it is absent, leave the set unchanged.
Return the search results in operation order. Inserts and deletes produce no output. Do not use a library ordered-set or tree-map container.
Follow-up discussion
State the cost of each operation in terms of tree height. Explain how sorted insertions can produce a chain and how AVL or red-black balancing would improve the worst case. The judged exercise does not require balancing.
Function
bstOperations(operations: int[][]) → int[]Examples
Example 1
operations = [[0,5],[0,3],[0,7],[1,3],[2,5],[1,5],[1,7]]return = [1,0,1]After the first three inserts, the keys are 3, 5, and 7. Searching for 3 succeeds. Deleting 5 removes only that key, so searching for 5 fails and searching for 7 succeeds.
Example 2
operations = [[0,2],[0,2],[2,9],[1,2],[2,2],[1,2]]return = [1,0]Inserting 2 twice still stores one key. Deleting the absent key 9 changes nothing. The searches before and after deleting 2 return 1 and 0.
Constraints
0 <= operations.length <= 5000.- Each operation has exactly two integers.
- The operation code is 0, 1, or 2.
-10^9 <= key <= 10^9.
More Citadel Phone Screen questions
- Portfolio Tickers with Constant-Time Random PickPHONE SCREEN · Seen Nov 2026
- Square Root FunctionPHONE SCREEN · Seen Oct 2026
- Reachable Transfer PositionsPHONE SCREEN · Seen Oct 2026
- Spreadsheet Formula DependenciesPHONE SCREEN · Seen Oct 2026
- Merge Price-Delta FeedsPHONE SCREEN · Seen Sep 2026
- Reconcile Unmatched Trades with Timestamp TolerancePHONE SCREEN · Seen Sep 2026
- Top Ten Trades by Notional ValuePHONE SCREEN · Seen Sep 2026
- Exchange BBO and Market-Wide NBBOPHONE SCREEN · Seen Sep 2026
- Maximize Workday EarningsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Changes for Palindromic BlocksOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Tree Selection and VisibilityJane Street · PHONE SCREENJane Street interview questions
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions
- Search for an Element in a StreamAmazon · PHONE SCREEN
- Build a File Tree from Streamed RecordsNextdoor · PHONE SCREENNextdoor interview questions
- Hierarchical In-Memory File SystemClay · PHONE SCREEN
- Throne Inheritance Without an Initial KingSnowflake · PHONE SCREENSnowflake interview questions
- Nested Todo ListNotion · PHONE SCREEN · ONSITE INTERVIEWNotion interview questions