Find the Lowest Common Ancestor in a Binary Tree
Company: Microsoft
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
# Lowest Common Ancestor in a Binary Tree
## Problem
A binary tree contains distinct integer values but has no ordering guarantee. You are given the tree in level-order form and two values, `p` and `q`, that are present in the tree. In the level-order list, `null` denotes a missing child.
Return the value of the lowest node whose subtree contains both `p` and `q`. A node may be an ancestor of itself.
### Function Contract
Implement `lowestCommonAncestor(levelOrder, p, q)`.
- Input: a level-order list containing integers and `null` markers, plus two integer values.
- Output: the integer value of the lowest common ancestor.
### Rules and Edge Cases
- The tree is non-empty, and all node values are distinct.
- Both target values occur in the tree.
- Do not rely on binary-search-tree ordering.
- Either target may be the root or an ancestor of the other target.
### Examples
```text
Input: levelOrder = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output: 3
```
```text
Input: levelOrder = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
```
```hint Let subtrees report discoveries
Think about what a recursive call should return when its subtree contains neither target, one target, or both targets.
```
```hint Combine results after visiting children
The first node that receives a non-empty result from both sides is the lowest branching point between the targets.
```
Quick Answer: Find the lowest common ancestor of two values in an unordered binary tree represented in level-order form. Practice recursive subtree reporting to identify the lowest branching point without relying on binary-search-tree ordering.
Implement lowest_common_ancestor(level_order, p, q). The nonempty list is a breadth-first serialization of a binary tree with null child markers: after the root, each existing node consumes the next left and right child slots. Values are distinct, p and q are present, and no ordering property is available. Return the lowest common ancestor's value.
Constraints
- 1 <= level_order.length <= 15.
- level_order is a valid trimmed breadth-first serialization with null child markers.
- Every non-null value is a distinct integer from -3,000,000,000 through 3,000,000,000.
- p and q are values present in the tree and may be equal.
- No binary-search-tree ordering may be assumed.
Examples
Input: ([5], 5, 5)
Expected Output: 5
Explanation: A single target node is its own lowest common ancestor.
Input: ([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], 5, 1)
Expected Output: 3
Explanation: The targets are found in opposite root subtrees.
Hints
- Let each subtree report whether it found neither target, one target, or an ancestor containing both.
- The first node with nonempty results from both children is the lowest branching point.
- If the current node is a target, return it so ancestor-target cases remain correct.