Find LCA in a N-ary tree via DFS

You are given the root of a rooted N-ary tree (each node can have zero or more children) and two distinct nodes p and q that belong to the tree.

Design an algorithm to find the lowest common ancestor (LCA) of p and q.

The LCA of two nodes p and q in a rooted tree is defined as the lowest (i.e., deepest) node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Input

• A reference to the root node of an N-ary tree.
  Each node has:
  • A value.
  • A list of child nodes.
• Two references p and q to distinct nodes in the same tree.

Output

• A reference to the node that is the LCA of p and q .

Constraints

• The tree can have up to $10^5$ nodes.
• The tree is not necessarily balanced.
• Node values may not be unique; you must work with node references, not just values.

Requirements

1. Describe a recursive DFS-based algorithm that finds the LCA in a single traversal of the tree.
2. Your DFS helper for each node should conceptually return a pair of booleans (or equivalent) indicating whether p or q was found in that node’s subtree.
   • The first node where both flags are true in the returned pair should be identified as the LCA.
3. Implement this algorithm in your preferred programming language.
   • You may define your own N-ary tree node structure (e.g., with a children list).

Explain the algorithm and then provide the implementation.