How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Scale AI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Scale AI during technical interviews.

Find LCA in a N-ary tree via DFS | Scale AI Coding Question

Find LCA in a N-ary tree via DFS

Company: Scale AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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 a rooted N-ary tree and two distinct nodes p and q. Find their lowest common ancestor (LCA) using one recursive DFS traversal. For this coding version, the tree is serialized as (id, value, children), where id is unique, value may be duplicated, and children is a list of child nodes in the same format. The ids p_id and q_id act as stand-ins for node references. Your DFS helper should return a pair of booleans indicating whether p or q appears in the current subtree. Because the traversal is postorder, the first node whose subtree reports both booleans is the LCA.

Constraints

1 <= number of nodes <= 10^5
The tree may be highly unbalanced
Node ids are unique, but node values may repeat
p_id and q_id are distinct and both exist in the tree

Examples

Input: ((1, 100, [(2, 200, [(5, 500, []), (6, 600, [])]), (3, 300, []), (4, 400, [(7, 700, []), (8, 800, [])])]), 5, 8)

Expected Output: 1

Explanation: Node 5 is in the subtree of 2 and node 8 is in the subtree of 4, so their lowest common ancestor is the root node 1.

Input: ((1, 100, [(2, 200, [(5, 500, []), (6, 600, [])]), (3, 300, []), (4, 400, [(7, 700, []), (8, 800, [])])]), 5, 6)

Expected Output: 2

Explanation: Nodes 5 and 6 are both direct children of node 2, so node 2 is their LCA.

Hints

Let each DFS call return two booleans: whether p was found in the current subtree and whether q was found in the current subtree.
Use postorder traversal. If children are processed before the current node, the first node whose returned pair becomes (True, True) is the deepest common ancestor.

Quick Overview

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.