How do you find the lowest common ancestor with parent pointers?

Walk from the first node up to the root and put every node you pass into a set. Then walk from the second node upward and stop at the first node that is in the set; that is the lowest common ancestor. Both walks take time proportional to the tree's depth. An alternative with no extra set is to measure both depths, lift the deeper node until the depths match, then move both up together until they meet.

How do you find the LCA of more than two nodes?

Fold the two-node answer across the list. Start with the first node, then replace the running answer with the LCA of it and the next node, until the list is used up. This works because the lowest common ancestor of a group is the same no matter how you pair them up. With k nodes the cost is k two-node queries. A single node is its own answer.

How do you check if one employee is above another in an org chart?

Walk upward from the lower employee through their manager, then that manager's manager, and so on to the top. If you meet the other person on the way, they are above. The walk is as long as the depth of the tree. The same check tells you whether moving someone under a new manager is safe: it is not when the employee appears on the new manager's upward chain.

AceOffer·

MediumAbout 40 minFree

Helpful?Is this question helpful?

Back

Part 1 · Reports and chain of command

You are given (employee, manager) pairs. Names are unique strings and the top-level employee has manager None. Pairs can come in any order, every manager named also appears as an employee, and the input always forms one valid tree.

pairs = [
    ("Ana", None),
    ("Ben", "Ana"), ("Cal", "Ana"),
    ("Dee", "Ben"), ("Eve", "Ben"),
    ("Fay", "Cal"),
    ("Gil", "Dee"), ("Hue", "Dee"),
]

Ana
  Ben
    Dee
      Gil
      Hue
    Eve
  Cal
    Fay

Implement OrgChart(pairs) with two methods.

reports_count(name) -> int: how many people are under name, directly or indirectly. name is not counted.
chain_of_command(name) -> list[str]: name, then their manager, and so on up to the top-level employee.
Both raise KeyError for a name not in the chart.
A chart can be thousands of levels deep, so avoid recursion that would hit Python's recursion limit.

org.reports_count("Ben")       # 4
org.chain_of_command("Gil")    # ["Gil", "Dee", "Ben", "Ana"]

Clarify before coding5 questions ▸

Does the count include indirect reports, and does it include the person themselves?
If one person is above the other, is that person the answer for lowest common manager?
For a group of people, is the answer the lowest manager shared by all of them?
In part 3, does moving someone take their whole team with them?
Is anyone 'above' themselves, and are two people with no manager peers?

Covers the whole problem: what candidates report interviewers adding on questions with this pattern, the mistakes to avoid, and where to go next.

What candidates report interviewers add

Find the lowest shared manager of a whole group of employees, not just two.3 reports · Amazon, Google · Part 2

Walk through several ways to find the common ancestor and compare their time and space costs.2 reports · Amazon, Uber

Solve it on a binary search tree first, then for a tree with no ordering.2 reports · Microsoft

Record reporting relationships one at a time and answer whether one person manages another or shares a manager with them.1 report · Google · Part 3

Return everyone under a given person, directly or indirectly.1 report · Microsoft

Why practise this

Tree recursion and traversal shows up in 12.2% of the 1,447 coding interview reports we studied, at 13 companies. Aggregate values up a tree, find or remove nodes, or work with parent-child records that have to be assembled into a tree first.

Reported at: OpenAI, Anthropic, Databricks, Snowflake, Amazon, Waymo, Citadel, Zip, Roblox, Rippling, Robinhood, Mercor.

This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.

Common mistakes5 ▸

Counting the person in their own report count, or only counting direct reports.
Recursing down a long chain and hitting Python's recursion limit.
Splitting a group of employees into halves for the group question; folding the pairwise answer is simpler and correct.
Moving an employee without removing them from their old manager's report list.
Keeping cached report counts after a move, so later answers are stale.

Where an interviewer could take it next3 ▸

Answer many lowest-common-manager queries fast, for example with binary lifting.
Print the chart as indented text with reports sorted by name.
List everyone exactly k levels below a given person.

Frequently asked3 ▸

How do you find the lowest common ancestor with parent pointers?: Walk from the first node up to the root and put every node you pass into a set. Then walk from the second node upward and stop at the first node that is in the set; that is the lowest common ancestor. Both walks take time proportional to the tree's depth. An alternative with no extra set is to measure both depths, lift the deeper node until the depths match, then move both up together until they meet.
How do you find the LCA of more than two nodes?: Fold the two-node answer across the list. Start with the first node, then replace the running answer with the LCA of it and the next node, until the list is used up. This works because the lowest common ancestor of a group is the same no matter how you pair them up. With k nodes the cost is k two-node queries. A single node is its own answer.
How do you check if one employee is above another in an org chart?: Walk upward from the lower employee through their manager, then that manager's manager, and so on to the top. If you meet the other person on the way, they are above. The walk is as long as the depth of the tree. The same check tells you whether moving someone under a new manager is safe: it is not when the employee appears on the new manager's upward chain.

Practise next

Log File Parser · Parsing structured text CSV Join and Group By · Hash-map counting, grouping and joins Time-Based Key-Value Store with TTL · Time-based state (expiry, TTL, snapshots)

Preparing for a specific company? The company guides collect the questions candidates report, with every part and follow-up.

Python 3

Tests5 tests · not run yet

Run the part to execute this test.

Expected

Ana 7
Ben 4
Cal 1
Dee 2
Gil 0

Test code

pairs = [
    ("Ana", None),
    ("Ben", "Ana"), ("Cal", "Ana"),
    ("Dee", "Ben"), ("Eve", "Ben"),
    ("Fay", "Cal"),
    ("Gil", "Dee"), ("Hue", "Dee"),
]
org = OrgChart(pairs)
for n in ["Ana", "Ben", "Cal", "Dee", "Gil"]:
    print(n, org.reports_count(n))

Lowest Common Manager (Org Chart)

Medium3 partsabout 40 minTree recursion and traversal Hash-map counting, grouping and joins DFS and connected components

Build an org chart from (employee, manager) pairs, count reports and walk the chain of command, find the lowest common manager of two or more people, then support moving people around and asking who sits above whom.

Also known as: Lowest common ancestor of an n-ary tree, Employee hierarchy, Lowest common manager

Why practise this

Reported at: OpenAI, Anthropic, Databricks, Snowflake, Amazon, Waymo, Citadel, Zip, Roblox, Rippling, Robinhood, Mercor.

This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.

What candidates report interviewers add

Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.

Find the lowest shared manager of a whole group of employees, not just two.3 reports · Amazon, Google · Part 2
Walk through several ways to find the common ancestor and compare their time and space costs.2 reports · Amazon, Uber
Solve it on a binary search tree first, then for a tree with no ordering.2 reports · Microsoft
Record reporting relationships one at a time and answer whether one person manages another or shares a manager with them.1 report · Google · Part 3
Return everyone under a given person, directly or indirectly.1 report · Microsoft

pairs = [
    ("Ana", None),
    ("Ben", "Ana"), ("Cal", "Ana"),
    ("Dee", "Ben"), ("Eve", "Ben"),
    ("Fay", "Cal"),
    ("Gil", "Dee"), ("Hue", "Dee"),
]

Ana
  Ben
    Dee
      Gil
      Hue
    Eve
  Cal
    Fay

Questions to ask before you code

Does the count include indirect reports, and does it include the person themselves?
If one person is above the other, is that person the answer for lowest common manager?
For a group of people, is the answer the lowest manager shared by all of them?
In part 3, does moving someone take their whole team with them?
Is anyone 'above' themselves, and are two people with no manager peers?

Part 1: Reports and chain of command

Implement OrgChart(pairs) with two methods.

reports_count(name) -> int: how many people are under name, directly or indirectly. name is not counted.
chain_of_command(name) -> list[str]: name, then their manager, and so on up to the top-level employee.
Both raise KeyError for a name not in the chart.
A chart can be thousands of levels deep, so avoid recursion that would hit Python's recursion limit.

org.reports_count("Ben")       # 4
org.chain_of_command("Gil")    # ["Gil", "Dee", "Ben", "Ana"]

Part 2: Lowest common managerfrom reports

lowest_common_manager(a, b) -> str: the person lowest in the tree who appears in both chain_of_command(a) and chain_of_command(b). Because a person is in their own chain, if a is above b the answer is a, and lowest_common_manager(x, x) is x.
lowest_common_manager_of(names) -> str: the same for a list. A single name returns itself and repeated names are allowed. An empty list raises ValueError.
Unknown names raise KeyError.

org.lowest_common_manager("Gil", "Eve")              # "Ben"
org.lowest_common_manager_of(["Gil", "Hue", "Fay"])  # "Ana"

Part 3: Moves and relationship checksfrom reports

The chart now changes over time and gets asked yes/no questions.

set_manager(employee, manager) -> None: if employee is new, add them as a direct report of manager. If they already exist, move them (and everyone under them) so that manager becomes their direct manager. Raise KeyError if manager is not in the chart. Raise ValueError, changing nothing, if the move would create a loop, which happens when manager is employee or is anywhere under employee.
is_above(a, b) -> bool: True when a appears in chain_of_command(b) and a != b. So it is False for the same person.
are_peers(a, b) -> bool: True when a != b and both have the same direct manager. The top-level employee has no peers.
is_above and are_peers raise KeyError for unknown names.
All Part 1 and Part 2 methods must reflect the changes, including reports_count.

org.set_manager("Fay", "Ben")
org.reports_count("Ben")       # 5
org.are_peers("Fay", "Dee")    # True
org.is_above("Ana", "Gil")     # True

Open this page on a laptop or desktop to write and run your code against the tests in the browser.

Approach

Spoilers: try each part before reading its walkthrough.

Part 1: Reports and chain of command

The pairs describe a tree where each node stores its parent. Build two dicts in one pass: manager (employee to boss) for going up, and reports (boss to a list of employees) for going down. Pairs can arrive in any order, and since dicts are filled before any query, order does not matter. chain_of_command just follows manager until it hits None, which is O(depth). reports_count sums 1 + count(child) over the children. The reference does that with an explicit stack in post-order instead of recursion, because a chain thousands of levels deep would blow past the roughly 1000-frame recursion cap Python ships with. Results are cached in _count, so the first call is O(subtree size) and repeated calls are O(1).

Part 2: Lowest common manager

With parent pointers you do not need the classic recursive tree LCA. Collect everyone in chain_of_command(a) into a set, then walk chain_of_command(b) from the bottom up; the first name already in the set is the lowest shared manager. Because each chain starts with the person themselves, the case where one is above the other falls out naturally. Both walks are O(depth), and the set costs O(depth) memory. For a list of names, LCA is associative: the answer for [x, y, z] equals the answer for lca(lca(x, y), z). So the reference folds the pairwise call across the list, giving O(k x depth) for k names, and raises ValueError up front for an empty list.

Part 3: Moves and relationship checks

A move breaks the tree only if the new manager is the employee or sits beneath them, because then following managers upward from the new manager would come back to the employee. So the check is a single walk: employee in self.chain_of_command(manager), O(depth), and nothing changes when it fails. Otherwise unlink the employee from the old manager's report list, set the new manager, and append to the new list. The employee's own reports stay attached, so the whole team moves for free. Report counts change for everyone above both the old and the new position, so the reference clears the cache rather than patching it. is_above reuses the chain walk, and are_peers compares two dictionary lookups.

Hints

Part 1 hint

Keep two maps: employee to manager for walking up, and manager to list of reports for walking down. Counting reports is a DFS down that second map.

Part 2 hint

Put chain_of_command(a) in a set and walk chain_of_command(b) from the bottom; the first hit is the answer. For a list, fold the two-person answer across all names.

Part 3 hint

A move is safe unless the new manager sits under the employee, which you can test by looking for the employee in chain_of_command(new manager). Update both maps, then drop any cached counts.

Common mistakes

Counting the person in their own report count, or only counting direct reports.
Recursing down a long chain and hitting Python's recursion limit.
Splitting a group of employees into halves for the group question; folding the pairwise answer is simpler and correct.
Moving an employee without removing them from their old manager's report list.
Keeping cached report counts after a move, so later answers are stale.

Where an interviewer could take it next

Answer many lowest-common-manager queries fast, for example with binary lifting.
Print the chart as indented text with reports sorted by name.
List everyone exactly k levels below a given person.

Complexity

Building the chart is O(n) for n pairs. reports_count is O(subtree size) the first time and O(1) once cached. chain_of_command and lowest_common_manager are O(depth); lowest_common_manager_of over k names is O(k x depth). set_manager is O(depth) for the loop check plus O(number of direct reports) to unlink, and it clears the count cache. is_above is O(depth) and are_peers is O(1).

Frequently asked

How do you find the lowest common ancestor with parent pointers?: Walk from the first node up to the root and put every node you pass into a set. Then walk from the second node upward and stop at the first node that is in the set; that is the lowest common ancestor. Both walks take time proportional to the tree's depth. An alternative with no extra set is to measure both depths, lift the deeper node until the depths match, then move both up together until they meet.
How do you find the LCA of more than two nodes?: Fold the two-node answer across the list. Start with the first node, then replace the running answer with the LCA of it and the next node, until the list is used up. This works because the lowest common ancestor of a group is the same no matter how you pair them up. With k nodes the cost is k two-node queries. A single node is its own answer.
How do you check if one employee is above another in an org chart?: Walk upward from the lower employee through their manager, then that manager's manager, and so on to the top. If you meet the other person on the way, they are above. The walk is as long as the depth of the tree. The same check tells you whether moving someone under a new manager is safe: it is not when the employee appears on the new manager's upward chain.

Practise next

Log File Parser

Parsing structured text

CSV Join and Group By

Hash-map counting, grouping and joins

Time-Based Key-Value Store with TTL

Time-based state (expiry, TTL, snapshots)

See what candidates report at each company

The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.

Browse the interview guides