Katkat
Back

Find LCA in a N-ary tree via DFS

Scale AISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of tree algorithms and recursive DFS traversal for computing the lowest common ancestor in an N-ary tree, including handling node references, subtree detection, and correctness in a single traversal.

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.
  1. 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.