Binary Tree Search
Updated
Problem statement
You are given the root of a binary search tree and an array of integers val.
In this tree, every value in a node's left subtree is less than the node's value, and every value in its right subtree is greater than or equal to the node's value.
For each val[i], check whether some node in the tree holds that value. Return an array of the same length as val where element i is 1 if val[i] is in the tree, and 0 otherwise.
Function
isPresent(root: TreeNode, val: int[]) → int[]Examples
Example 1
root = [20, 10, 30, 8, 12, 25, 40, 6, null, 11, 13, 23]val = [30, 10, 12, 15]return = [1, 1, 1, 0]Each search starts at the root 20. For 30: 30 > 20, go right to 30, found. For 10: 10 < 20, go left to 10, found. For 12: left to 10, then 12 > 10, right to 12, found. For 15: left to 10, right to 12, right to 13, then 15 > 13 but 13 has no right child, so 15 is not in the tree.
Example 2
root = [20, 10, 30, 8, 12, 25, 40, 6, null, 11, 13, 23]val = [79, 10, 20, 30, 40]return = [0, 1, 1, 1, 1]For 79: 79 > 20, right to 30, right to 40, and 40 has no right child, so it is not found. The values 10, 20, 30 and 40 are all in the tree.
Example 3
root = [8, 3, 8]val = [8, 3, 9]return = [1, 1, 0]The root is 8. Its left child is 3, and its right child is another 8, because equal values belong in the right subtree. 8 and 3 are found. For 9: 9 > 8 at the root, right to the second 8, which has no right child, so 9 is not found.
Constraints
- The number of nodes in the tree is in the range
[1, 105]. 1 <= Node.val <= 5 * 1041 <= val.length <= 1051 <= val[i] <= 5 * 104- The tree follows the binary search tree rule above.
More Airbnb Online Assessment questions
- Task Management SystemOA · Seen Nov 2026
- Recipe Management SystemOA · Seen Nov 2026
- Progressive Banking SystemOA · Seen Nov 2026
- Credit Accounts with Scheduled TransfersOA · Seen Oct 2026
- Parcel Attribute Store with TTLOA · Seen Oct 2026
- Parcel Event TrackingOA · Seen Oct 2026
- Median Home Price by CityOA · Seen Sep 2026
- In-Memory File SystemOA · Seen Sep 2026
- Worker Management (Promotion Track), Part 4: Full-Shift Double PayOA · Seen Sep 2026
- Worker Management (Promotion Track), Part 3: Promotions and SalaryOA · Seen Sep 2026
Similar questions at other companies
- Lowest Common Ancestor in a Parent TreeBlackRock · OABlackRock interview questions
- Palindromic Paths to the RootRippling · OARippling interview questions
- Build and Render an Organization Role TreeStripe · OAStripe interview questions
- Get Most Hydrated TeamAirtable · OAAirtable interview questions
- Merge Row Trees by Key PathHudson River Trading · OAHudson River Trading interview questions
- Find the Root of a Directed TreeAmazon · ONSITE INTERVIEW
- Mode of a Ternary Search TreeGoogle · PHONE SCREENGoogle interview questions
- Find Nodes with Invalid Parent LevelsZip · ONSITE INTERVIEWZip interview questions
- Tree Nodes with Zero or One ParentWayfair · PHONE SCREENWayfair interview questions
- Two Tree Values That Add Up to a TargetExpedia · ONSITE INTERVIEWExpedia interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)