Common ancestor in a page tree: A Sample Coding Interview Solution

The coding question

Confluence pages form a tree where every page except the root has one parent. Given many pairs of pages, return the lowest common ancestor of each pair.

Ask a few questions first

Ask	What we'll assume
How is the tree given?	A map from each page to its parent. The root's parent is None.
How many pages and queries?	Up to around 100,000 of each. That's why doing work once up front matters.
Can a page be its own ancestor?	Yes. If one page is above the other, it's the answer. A page paired with itself returns itself.
Do I get all the queries at once?	Assume yes, as a list of pairs. I'll make each query independent anyway, so it works one at a time too.
Could the tree be very deep, like a long chain?	Yes, so avoid recursion that could hit Python's depth limit.

A couple of examples

Input	Output
Home > Eng > API > Auth, Eng > Web, Home > HR > Leave. Pairs: (Auth, Web), (Auth, Leave)	[Eng, Home]
Same tree. Pairs: (API, Auth), (Web, Web)	[API, Web]
A chain 0 > 1 > ... > 99999. Pairs: (99999, 50000), (12345, 99999)	[50000, 12345]

Start with brute force

For each pair, walk up from the first page and put every page you pass in a set. Then walk up from the second page until you hit something in the set.

Cost: O(h) per query where h is the tree's height. For a long chain that's O(n), so 100,000 queries could take 10 billion steps.

A better way

Walking up one step at a time is what's slow. If each page knew the page 1 step up, 2 steps up, 4 steps up, 8 steps up and so on, you could jump up any distance in about log n moves. That's called binary lifting.

Building those tables is a bit like dynamic programming: the page 4 steps up is the page 2 steps up from the page 2 steps up. So each level is built from the one before.

With the tables, a query lifts the deeper page to the same depth using the binary bits of the difference. Then it tries the biggest jumps first, and only jumps both pages if they'd still land on different pages. After that, their parent is the answer.

Build a list of children for each page and find the root.
Walk the tree breadth first from the root to get every page's depth. No recursion, so deep chains are fine.
Level 0 of the jump table is each page's parent. The root points at itself so jumps never fall off the top.
Build each next level: jump[k][page] = jump[k-1][jump[k-1][page]].
For each query, lift the deeper page to match the other's depth.
If they're now the same page, that's the answer. If not, from the biggest jump down, jump both whenever they'd land on different pages. Return the parent of where they end.

The code

solution.pypython

from collections import deque


def lowest_common_ancestors(parent, queries):
    # parent maps each page to its parent page, and the root to None.
    children = {page: [] for page in parent}
    root = None
    for page, up in parent.items():
        if up is None:
            root = page
        else:
            children[up].append(page)

    # Depth of every page, found with a breadth-first walk from the root.
    depth = {root: 0}
    queue = deque([root])
    while queue:
        page = queue.popleft()
        for child in children[page]:
            depth[child] = depth[page] + 1
            queue.append(child)

    # jump[k][page] is the page 2**k steps above it (the root stays the root).
    levels = max(1, max(depth.values()).bit_length())
    jump = [{page: (up if up is not None else page) for page, up in parent.items()}]
    for k in range(1, levels):
        prev = jump[k - 1]
        jump.append({page: prev[prev[page]] for page in parent})

    def lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
        diff = depth[a] - depth[b]
        k = 0
        while diff:
            if diff & 1:
                a = jump[k][a]
            diff >>= 1
            k += 1
        if a == b:
            return a
        for k in range(levels - 1, -1, -1):
            if jump[k][a] != jump[k][b]:
                a = jump[k][a]
                b = jump[k][b]
        return jump[0][a]

    return [lca(a, b) for a, b in queries]

	Cost	Why
Setup time	O(n log n)	About log n levels, each covering all n pages
Time per query	O(log n)	At most log n jumps to line up the depths, and log n more to meet
Space	O(n log n)	The jump tables

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

A tree with only the root: every query is (root, root), and the answer is the root.
One page is an ancestor of the other: lifting gets them equal, so return straight away.
The same page twice: the depth difference is 0 and they're already equal.
A long chain of 100,000 pages: no recursion, so no depth limit errors.
No queries: return an empty list. The setup still runs, which is fine.

Common mistakes

Writing the depth search recursively. A 100,000-page chain blows past Python's default limit.
Letting the root's parent be None in the jump table, then crashing when a jump goes past the top. Point the root at itself.
Returning a or b at the end instead of their parent. The loop stops just below the meeting point.
Jumping both pages when they'd land on the same page. That could skip past the lowest one to a higher shared ancestor.

Follow-up questions

Can you do it with less setup memory?

Yes. Walk the tree once in order, recording each page every time you pass it. The common ancestor of two pages is the shallowest page between their first visits. With a table that answers 'minimum in a range' quickly, each query becomes constant time.

What if you get all queries at once and want the fastest total?

Tarjan's offline method answers every pair in one walk of the tree, using a union-find structure. It's close to linear in pages plus queries.

What if pages get moved around?

Moving a page changes the depth and jumps of everything under it. If moves are rare, rebuild. If they're common, the simple walk-up answer per query may be good enough, or you'd need much fancier structures.

How the time adds up

Minutes	What you're doing
0–5	Ask about sizes, the root, and how queries arrive
5–10	Brute force: walk up per query, and why it's too slow
10–20	Binary lifting: jump tables built level by level
20–35	Write the code
35–40	Test with the examples and a long chain
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Atlassian.