Closest Shared Mentor
A woodworking guild trains people by apprenticeship. The founder took on at most two apprentices, each of them later took on at most two of their own, and so on. The guild keeps this as a binary tree of membership numbers, with the founder at the root.
When two members disagree about technique, the guild asks the closest person in both of their training lines to settle it: the member furthest from the founder who trained both of them, directly or through others. If one of the two trained the other, that person settles it themselves.
Your task
Write closestSharedMentor(root, a, b). a and b are values of nodes in the tree. Return the value of their lowest common ancestor: the deepest node that has both a and b in its subtree. A node counts as being in its own subtree, so if a is an ancestor of b, the answer is a.
The tree is an ordinary binary tree, not a search tree: the numbers are in no particular order. All values are different, both a and b are in the tree, and they may be the same value. Trees are shown in level order with null for a missing child. Your function receives real TreeNode objects with val, left and right.
closestSharedMentor(root: TreeNode, a: int, b: int) → int
Examples
root = [8, 3, 11, 5, 1, 9, 14, null, null, 7, 4, null, null, 2, 6] a = 7 b = 4
1
7 and 4 are both apprentices of 1. Member 3 and the founder 8 also trained both of them indirectly, but 1 is the closest, the deepest node that has both below it.
root = [8, 3, 11, 5, 1, 9, 14, null, null, 7, 4, null, null, 2, 6] a = 1 b = 4
1
Member 1 trained member 4 directly. A member counts as being in their own line, so 1 settles it. The answer is not 3, the person above them.
Constraints
- 1 ≤ number of members ≤ 1,000
- -100,000 ≤ membership number ≤ 100,000, all different
- a and b are both in the tree.
- The tree is at most 500 levels deep.
Start with brute force
Find the path from the founder down to a, and separately the path down to b. Walk both paths together from the top; the last member they share is the answer.
That is O(n) and correct, but it walks the tree twice and stores two paths of up to 500 members. A trap to avoid: if you treat the tree as a search tree and go left or right by comparing numbers, you get wrong answers, because these numbers are not ordered. One bottom-up walk that reports what it found answers the question directly.
Hints
0 of 4 shown- Hint 1
Stand at member 3 in the first example and look down. On which side of 3 is member 7, and on which side is member 4? Now do the same at member 1.
- Hint 2
At 3, both people are on the same side (the right, under 1), so 3 is not the closest: going down to 1 keeps both. At 1, they split: one on the left, one on the right. The first node where they split is the answer.
- Hint 3
Let each subtree report back to its parent: "I found a or b here" (by returning that node) or "I found nothing" (null). What should a node conclude if both its left and right sides report something?
- Hint 4
Recurse: if the node is null, or its value is a or b, return the node. Otherwise ask both children. If both return a node, the current node is the answer. If only one does, pass that one up. The value of what reaches the root is the answer.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Each subtree reports one thing to its parent: the node it found (a, b, or their meeting point) or null. The first node that hears back from both sides is where the two lines split, and that is the answer.
Trace the first example, looking for 7 and 4:
- At 8, search left into 3. At 3, the left side (5) finds nothing and returns null.
- At 3's right child 1: its left child is 7, which matches, so it returns 7. Its right child is 4, which matches, so it returns 4.
- Node 1 heard from both sides, so it returns itself.
- 3 heard from one side only (1), so it passes 1 up. At 8, the right side (11) finds nothing. 8 passes 1 up, and the answer is 1.
The ancestor case works by itself: searching for 1 and 4, the search stops at 1 and returns it without looking below, and nothing else reports back, so 1 is passed up to the top.
function closestSharedMentor(root, a, b) {
// Returns a node holding a or b found in this subtree,
// or their meeting point once both have been found.
function search(node) {
if (node === null || node.val === a || node.val === b) return node;
const left = search(node.left);
const right = search(node.right);
if (left !== null && right !== null) return node; // they split here
return left !== null ? left : right;
}
return search(root).val;
}def closest_shared_mentor(root, a, b):
# Returns a node holding a or b found in this subtree,
# or their meeting point once both have been found.
def search(node):
if node is None or node.val == a or node.val == b:
return node
left = search(node.left)
right = search(node.right)
if left is not None and right is not None:
return node # they split here
return left if left is not None else right
return search(root).valRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.