Common Parent in a Tree | Dataford Interview Questions

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 question is Common Parent in a Tree. Start with the requirements in the Question tab.

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

Problem

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 question is Common Parent in a Tree. Start with the requirements in the Question tab.

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