Katkat
Back

Find LCA in a tree and extend to a DAG

AtlassianMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your understanding of tree traversal, graph theory, and how to generalize path-finding algorithms from trees to directed acyclic graphs (DAGs).

Part 1: Tree LCA

Given the root of a binary tree and two nodes p and q, find the lowest common ancestor (LCA) of the two nodes. The LCA is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

Part 2: DAG LCA

Now, consider a Directed Acyclic Graph (DAG) where each node can have multiple parents. Define the "lowest" common ancestor as a node A such that A is an ancestor of both p and q, and there is no descendant of A that is also an ancestor of both p and q.

Task

  1. Implement a function findTreeLCA(root, p, q) for a standard binary tree.
  2. Provide an approach to find the LCA in a DAG. Since a DAG may have multiple nodes satisfying the ancestor criteria, discuss how to return all valid LCAs.

Constraints

  • The tree/graph size N is up to 10^5.
  • For the tree, your solution should aim for O(N) time complexity.
  • For the DAG, describe the complexity of your proposed solution.

Example (Tree)

Input: root = [3, 5, 1, 6, 2, 0, 8], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example (DAG)

If node C is a parent of D and E, and D and E are both parents of F, then C is an ancestor of F. If we have two paths, we are looking for the "deepest" shared ancestors.

Hints

Hint 1

For the tree, use a recursive approach to track whether the current node or its subtrees contain p or q.

Hint 2

In a DAG, a node can be an ancestor through multiple paths; use a set of ancestors for each node, which can be computed via topological sort or memoized DFS.

Hint 3

To find the lowest common ancestors in a DAG, first compute the set of all common ancestors and then filter out nodes that have a child who is also a common ancestor.

Follow-up questions

  • How does the time complexity change if you need to perform Q queries on the tree?
  • If the DAG is very large and doesn't fit in memory, what storage strategy would you use?
  • How would you handle a cycle if the graph provided is not actually a DAG?