FastPrepLowest Common Ancestor with Repeated and Missing Values
Problems/Lowest Common Ancestor with Repeated and Missing Values

Lowest Common Ancestor with Repeated and Missing Values

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2025 Expedia software engineering intern candidate, interviewed when Expedia visited their campus, got this in the first of two interviews held there. It was a lowest common ancestor question on a binary tree with two twists. Values can repeat, and one or both targets might be missing.

The report does not say what a repeated value means or what to return for a missing target. Here, a target value stands for every node that holds it. The answer is the lowest node that is an ancestor of all of those nodes, counting a node as its own ancestor. p and q may also be the same value. If either value is on no node, the answer is -1. You return the answer node's value. The tree is given in the usual level-order form, with up to 10^4 nodes and values from 0 to 10^9. These rules, the limits and the examples are our choices.

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

You are given the root of a binary tree and two target values p and q. Values in the tree can repeat, so a target value may be on many nodes, on one node, or on no node at all.

Call a node a target node if its value is p or q. If no node has the value p, or no node has the value q, return -1.

Otherwise, return the value of the lowest common ancestor of all target nodes: the deepest node that is an ancestor of every target node. A node counts as an ancestor of itself. The values p and q may be equal.

Node values are never negative, so -1 can only mean that a target value is missing.

Function

lowestCommonAncestorOfValues(root: TreeNode, p: int, q: int) → int

Examples

Example 1

root = [8,3,9,4,7,4,2,null,null,1,5]p = 4q = 1return = 8
root
834715942

The value 4 is on two nodes: the left child of 3 and the left child of 9. The value 1 is on one node, below 7. Node 3 is above the first 4 and the 1, but not above the second 4, which is under 9. The only node above all three target nodes is the root, so the answer is 8.

Example 2

root = [2,2,6,null,5]p = 2q = 10return = -1
root
2256

The value 2 is on two nodes, but no node has the value 10. One target value is missing, so the answer is -1.

Example 3

root = [6,1,9,1,3]p = 1q = 3return = 1
root
61139

The value 1 is on the left child of the root and on that node's left child. The value 3 is that node's right child. The upper node with value 1 is above both of the other target nodes, and a node counts as its own ancestor, so it is the lowest common ancestor. The answer is its value, 1.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • 0 <= Node.val <= 10^9
  • 0 <= p, q <= 10^9

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
  • 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
  • Maximum Supplier ProfitONSITE INTERVIEW · Seen Aug 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 SWE Intern Final Round: 126 Experiences (Part 1 of 6)

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)
All Expedia interview questionsSee Expedia 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 lowestCommonAncestorOfValues(TreeNode root, int p, int q) {
        // Write your code here.
    }
}
Checking account…