Two Tree Values That Add Up to a Target
Updated
Problem statement
You are given root, the root of a binary tree, and an integer target. The tree is not necessarily a binary search tree, and values can repeat.
Find two different nodes whose values add up to target. A node cannot be paired with itself, but two different nodes may hold the same value.
Return the two values as [a, b] with a <= b. If more than one pair works, return the one with the smallest a (then b = target - a is fixed). If no pair works, return an empty array.
Function
findTargetPair(root: TreeNode, target: int) → int[]Examples
Example 1
root = [5,8,-2,1,null,6,11]target = 9return = [-2,11]Two pairs of nodes add up to 9: 1 + 8 and -2 + 11. The one with the smaller first value is -2 + 11, so the answer is [-2, 11]. The tree is not a binary search tree (8 is the left child of 5).
Example 2
root = [4,7,null,4]target = 8return = [4,4]Two different nodes both hold 4, and 4 + 4 = 8. No pair using 7 works, because no node holds 1.
Example 3
root = [3,-6,10]target = 6return = []The sums of different nodes are -3, 13 and 4. The value 3 would need a second node holding 3, and there is only one, so no pair works.
Constraints
- The number of nodes in the tree is in the range
[1, 5000]. -10^4 <= Node.val <= 10^4-2 * 10^4 <= target <= 2 * 10^4
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Sparse Vector Dot Product from TuplesMeta · ONSITE INTERVIEWMeta interview questions
- Lowest Common Ancestor with Parent PointersAdobe · ONSITE INTERVIEWAdobe interview questions
- Find the Root of a Directed TreeAmazon · ONSITE INTERVIEW
- Two SumMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Find Nodes with Invalid Parent LevelsZip · ONSITE INTERVIEWZip interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Render an Org Chart and Find Skip-Level PairsSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- 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
- Shortest Window with Required CountsOracle · ONSITE INTERVIEWOracle interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)