Lowest Common Ancestor in a Binary Tree
Updated
Problem statement
Given a nonempty binary tree and target values p and q, return the value of their lowest common ancestor: the deepest node that is an ancestor of both targets.
All node values are unique and both targets exist. A node is an ancestor of itself, so the two target values may be equal. The tree need not be a binary search tree.
Function
lowestCommonAncestorValue(root: TreeNode, p: int, q: int) → intExamples
Example 1
root = [3,5,1,6,2,0,8,null,null,7,4]p = 5q = 1return = 3The first common ancestor is the root.
Example 2
root = [3,5,1,6,2,0,8,null,null,7,4]p = 5q = 4return = 5Node 5 is an ancestor of itself and node 4, so its value is the answer.
Example 3
root = [1,2]p = 1q = 2return = 1The root is one of the requested nodes.
Constraints
- The tree contains 1 through 500 nodes.
-1000000000 <= node.val, p, q <= 1000000000.- The input is a nonempty valid binary tree with unique node values; both target values occur in it.
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
- 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
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)