Common Parent in a Tree

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Common Parent in a Tree. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Wix Editor represents a page as a rooted component tree. Given the root of this tree and the IDs of two components, return the ID of their lowest common ancestor, meaning the deepest component that contains both target components in its subtree.

Implement lowest_common_parent(root, id1, id2). Each node is represented as a dictionary with a unique string id and a children list. The two target IDs may refer to the same node. If either target is absent, return None.

The tree is not necessarily binary, and a target may be the root or an ancestor of the other target. Do not assume that children are ordered or that the tree is balanced.

Constraints

The tree contains 1 <= n <= 10^5 nodes
Every node ID is unique and is a non-empty string
Each node has a children list
The tree has no cycles
The tree may be highly unbalanced

Function Signature

def lowest_common_parent(root, id1, id2):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output