Nearest Common Manager
MediumTrees
Problem
A company's reporting lines form a binary tree: each employee (a distinct integer ID) has at most two direct reports. It is not a search tree.
Given two different IDs p and q that both exist, return the ID of their nearest common manager: the deepest node that has both in its subtree. An employee counts as part of their own subtree, so if p manages q (directly or indirectly), the answer is p.
Example 1
- Input:
- root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
- Output:
- 3
Example 2
- Input:
- root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
- Output:
- 5
4 reports to 2, who reports to 5.
Constraints
- 2 ≤ number of nodes ≤ 10^5
- -10^9 ≤ node.val ≤ 10^9
- All values are distinct; p ≠ q and both are present.
Hint
Show the first hint
Without ordering, you cannot tell from a comparison which side a value is on. What information would let you walk upward from p and q?
Walkthrough
How to approach it
01Clarify before coding
- Is it a search tree? No, so value comparisons do not tell direction.
- Are both IDs present? Yes.
- How deep can the tree be? Up to 10^5 nodes in a line, so avoid recursion in Python.
02Brute force
For each node, check (with a full subtree search) whether it contains both p and q, and keep the deepest such node.
Cost: O(n²) time: each of n nodes may search a subtree of size O(n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.